Sample Data Structures Questions Chapter 10 Trees (provide correct specific shor

Question

Sample Data Structures Questions
Chapter 10
Trees (provide correct specific short answer in c++)

Using the binary_tree_node from Section 10.3, write a recursive function to meet the following specification. You do not need to check the precondition.

template

int tree_depth(binary_tree_node* root_ptr)

// Precondition: root_ptr is the root pointer of a binary tree.

// Postcondition: The return value is the depth of the binary tree.

// NOTES: The empty tree has a depth of -1 and a tree with just a root

// has a depth of 0.

Explanation / Answer

Please find the C++ code for:-

int tree_depth(binary_tree_node* root_ptr){
// Corner case. Should never be hit unless the code is
// called on root_ptr = NULL
if (root_ptr == NULL)
return 0;

// Base case : Leaf Node. This accounts for height = 1.
if (root_ptr->left == NULL && root_ptr->right == NULL)
return 1;

// If left subtree is NULL, recur for right subtree
if (!root_ptr->left)
return tree_depth(root_ptr->right) + 1;

// If right subtree is NULL, recur for left subtree
if (!root_ptr->right)
return tree_depth(root_ptr->left) + 1;

return min(tree_depth(root_ptr->left), tree_depth(root_ptr->right)) + 1;
}

Please let me know in case of any clarifications required. Thanks!

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.