CODEWITHSUNDEEP
javarecursiondata-structuresbinary-search-tree
Monica Hübner
Monica Hübner

Reputation: 279

How the recursive procedure works for computing height of the BST?

I have a binary tree and the height is computed based on the following codes -

public int height(Node root) {

    if (root == null)
        return -1;

    Node focusNode = root; 
    int leftHeight = focusNode.leftChild != null ? height( focusNode.leftChild) : 0;
    int rightHeight = focusNode.rightChild != null ? height( focusNode.rightChild) : 0;
    return 1 + Math.max(leftHeight, rightHeight);

}

If the left or the right child of the root is not null, it again calls the same height method and recursion proceed. Otherwise, it returns zero. It's hard for me to understand how to counting increases ( say, like c +=1 you see it adds 1 for every loop).

Can anyone explains it to me in little details ?

Upvotes: 0

Views: 170

Answers (2)

dhke
dhke

Reputation: 15408

Let's use a simple example tree:

  r
 / 
A

To determine its height, we start at r. To calculate the height of the subtree below r, we first calculate the height of the left child tree and then the height of the right subtree. Then we pick the higher subtree and add 1 to its height (i.e. we add the height of r (1) to the higher subtree).

int leftHeight = focusNode.leftChild != null ? height( focusNode.leftChild) : 0;
// if the left subtree exists, calculate its height.
// the height is zero if there is no left subtree

Now, the height of the left subtree is the height of the tree rooted at A (ignore that r exists for the moment). Recursion says, the height of the tree rooted at A is again the height of the highest of its subtrees plus 1. The left subtree of A is NULL, so its height is 0. The right subtree of A is also NULL, so its height is also 0.

Hence the height of the subtree rooted at A has height max(0, 0) + 1 which is also the number we return back up to r: The height of r's left subtree is 1.

int rightHeight = focusNode.rightChild != null ? height( focusNode.rightChild) : 0;
// if the right subtree exists, calculate its height.
// the height is zero if there is no right subtree

Now we go right. r's right subtree is NULL, its height is thus 0.

So r has a subtree with height 1 (left) and a subtree with height 0 (right). We choose the height of the higher subtree and add 1. 

return 1 + Math.max(leftHeight, rightHeight);
// pick higher subtree and add 1 to its height
// to include the root node.

Hence the height of the tree rooted at r has height 2.

Note that there's no loop involved, only recursion. The problem is solved by solving the problem for each (smaller) subtree first and combining the results.

Upvotes: 0

Eran
Eran

Reputation: 394146

The count increases here :

return 1 + Math.max(leftHeight, rightHeight);

since each recursive call returns 1 + the higher of the results of the last two recursive calls.

Upvotes: 2

Related Questions