C++ *21.3 (Depth of BST) Add a function in BST to return the depth of the tree.
ID: 3597613 • Letter: C
Question
C++
*21.3 (Depth of BST) Add a function in BST to return the depth of the tree.
// Return the height of this binary tree. Height is the
// number of nodes in the longest path from the root
Int height()
Your sample output should show the sentence:
"DURING the whole of a dull, dark, and soundless day in the autumn of the year, when the clouds hung oppressively low in the heavens, I had been passing alone, on horseback, through a singularly dreary tract of country; and at length found myself, as the shades of the evening drew on, within view of the melancholy House of Usher."
Parsed and input into a binary search tree. It should display the tree with an inorder traversal. Run the height() function and display the results.
should be entered as shown
Explanation / Answer
the code structure is as follows :
------------------------------------------------------------------------------------------------
/* In a BST there are atmost two children for each node */
/* in this as there not much details for me to answer
* i am considering each node in BST is of userdefined datatype NODE
* and each node has a link to right child as right and
* left child as left
*/
// height calculates the depth of the BST
// as you asked that it should print the values in inorder
// traversal, i made it recursive so that calculating height and
// traversal happen in the same call.
int height(){
int hL,hR;
std :: cout << root->getValue(); // print the node value
hL = 1 + height(root->left);// calculate height of Left subtree
hR = 1 + height(root->right);// calculate height of right subtree
if(hL > hR)// if left height is greater return left height
return hL;
else //else return right height
return hR;
}
/* overloaded height method which takes argument of Node type */
int height(Node* node){
int hl,hr;
if(node != nullptr){// handling for nullnode
std :: cout << node -> getValue(); // print nnode value
hl = 1 + height(node->left);// calculate height of Left subtree
hr = 1 + height(node->right);// calculate height of right subtree
if(hl>hr)// if left height is greater return left height
return hl;
else //else return right height
return hr
}
// return 0 if node is null i.e., there is no depth for this
return 0;
}
---------------------------------------------------------------------------------------------
/* hope this helps */
/* if any queries, please comment */
/* thank you */
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.