What is recursive algorithm to find the height of a binary search tree with n numbers of nodes?

Answer 1

Really the best way to traverse any binary tree is recursion. In this case we are going to be some node defined as having 3 values, a pointer to a left node, a pointer to a right node, and a value.

then in psudocode we can do it as:

int height(node n, int depth){

int leftDepth;

int rightDepth;

if(n.left != NULL)

leftDepth = height(n.left, depth+1)

else

leftDepth = depth;

if(n.right != NULL)

rightDepth = height(n.right, depth+1)

else

rightDepth = depth;

if(leftDepth > rightDepth) return leftDepth;

return rightDepth;

}

Essentially what you are doing is calling the algorithm on both the left and right nodes which in turn will call it on their left and right nodes, down to where all the nodes are null. Then what is returned is the greater depth of the two; because it will traverse before returning a depth, and only traverses if there is a deeper node, it will return the depth of the deepest node, or the height of the binary tree.

Answer 2

int maxDepth( Node* node /* = NULL */ )

{

if( !node )

return( 0 );

int l = maxDepth( node->left );

int r = maxDepth( node->right );

return( 1 + ( l>r?l:r ));

}