What is the principle of calculating the height of binary tree by recursive method?

Question

This is the code that can find the height of the binary tree.

int PostOrderGetHeight(BinTree BT) { 
   int HL,HR,MaxH; 
   if(BT){ 
   HL = PostOrderGetHeight(BT->Left); 
   HR = PostOrderGetHeight(BT->Right); 
   MaxH = (HL>HR)?HL:HR;
   return (MaxH+1); 
   }
   else return 0;
}

My confusion is why HL, HR, MaxH don't need initialization and how does this recursive algorithm work to calculate the HL and HR.

None are used before they are set, so initialization is not needed. — stark, Aug 20 '19 at 14:50
@stark I see. But how can HL and HR be calculated? I can't understand this recursive algorithm... — Qizijia, Aug 20 '19 at 14:57
@齐子佳 do you understand induction and recursive calculations in general? E.g. that there is a base case and a recursive case, and that it is the base case that sets `HL` + `HR` here. If not, try reading up on wikipedia, maybe here: https://en.wikipedia.org/wiki/Recursion_(computer_science) — Morten Jensen, Aug 20 '19 at 15:00
`HL`, `HR` and `MaxH` do not need initialization because they are assigned values before there values are used in later expressions. You know that each recursion has its own `HL`, `HR` and `MaxH` variables, right? — Ian Abbott, Aug 20 '19 at 15:09
It finds the height by determining the height of the left and right sub-trees, determining which one of those is the largest, and adding 1 for its own node. An empty (sub-)tree has height 0. — Ian Abbott, Aug 20 '19 at 15:12

score 3 · Accepted Answer · answered Aug 20 '19 at 15:04

What you're doing here is calculating the height of both sides of each tree. Every binary tree will have a right and left tree, which will have it's own height, until it reaches a terminal node with no height on either side.

Lets go through this example.

We pass in A.
It tries to calculate the height of B (a's left tree).
- B tries to calculate the height of D (it's left tree).
  - D tries to calculate the height of it's left tree, and it returns zero.
  - D tries to calculate the height of its right tree (e)
  - e has no right or left trees (both return zero), so it return the max of (0) + 1 as it's height
- The max of D's right and left trees is 1, so the height of D is 1+1 = 2.
- B has no right node so that returns zero.
- The max of B's right and left nodes is 2, so B returns 2 +1 =3.
- A calculates the height of C (it's right node, which will return 1)
- Max of a's right and left is 3+1 =4.

score 2 · Answer 2 · answered Aug 20 '19 at 15:01

If BinTree BT is not equal to NULL then HL and HR get their values due to these statements

   HL = PostOrderGetHeight(BT->Left); 
   HR = PostOrderGetHeight(BT->Right);

Otherwise if for example BT, or BT->Left, or BT->Right are equal to NULL then a function call as for example

PostOrderGetHeight(BT->Left);

returns 0 because the function is defined like

int PostOrderGetHeight(BinTree BT) { 
   int HL,HR,MaxH; 
   if(BT){ 
      //...
   }
   else return 0;
        ^^^^^^^^ 
}

In each iteration of recursive calls of the function there is selected the maximum length between the left sub-tree and the right sub-tree.

Eric Postpischil · Answer 3 · 2019-08-20T15:14:03.363

We can provide PostOrderGetHeight works for any tree by:

proving it works for a tree of height 0, and
proving that if it works for a tree of height h−1 or less, with h > 0, then it works for a tree of height h.

Thus, we will have proven it works for a tree of height 0, and therefore it works for a tree of height 1, and therefore for a tree of height 2, and 3, and so on.

To prove the first part, suppose PostOrderGetHeight is called with a tree of height 0. This means its root node, BT is null. In this case, when the routine is called the else return 0; statement executes, and the routine returns zero, which is correct.

To prove the second part, suppose PostOrderGetHeight is called with a tree of height h, with h > 0.

Then these two statements are executed:

HL = PostOrderGetHeight(BT->Left); 
HR = PostOrderGetHeight(BT->Right);

Observe that each of these calls PostOrderGetHeight with subtree of BT. Each subtree, BT->Left and BT->Right, must be a tree of height less than h. Since we have assumed PostOrderGetHeight works for trees of height up to h@-1, it returns the correct heights for these trees.

Then MaxH = (HL>HR)?HL:HR; sets MaxH to whichever is greater, the height of the left subtree or the height of the right subtree. At this point, we know that BT has height one greater than that maximum, because it includes that larger subtree plus one more node (the root node BT).

Then the statement return (MAXH+1); returns that height.

score 0 · Answer 4 · answered Aug 20 '19 at 15:00

#include<stdio.h> 
#include<stdlib.h> 


struct node  
{ 
    int data; 
    struct node* left; 
    struct node* right; 
}; 

int maxDepth(struct node* node)  
{ 
   if (node==NULL)  
       return 0; 
   else 
   { 

       int lDepth = maxDepth(node->left); 
       int rDepth = maxDepth(node->right); 


       if (lDepth > rDepth)  
           return(lDepth+1); 
       else return(rDepth+1); 
   } 
}  


struct node* newNode(int data)  
{ 
    struct node* node = (struct node*) 
                                malloc(sizeof(struct node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 

    return(node); 
} 

int main() 
{ 
    struct node *root = newNode(1); 

    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5);  

    printf("Height of tree is %d", maxDepth(root)); 

    getchar(); 

}

Hope this helps!

This does not explain anything. – Eric Postpischil Aug 20 '19 at 15:08 — Eric Postpischil, Aug 20 '19 at 15:08

score 0 · Answer 5 · answered Aug 20 '19 at 15:09

Perhaps it is clearer to declare and initialise the variables in one step. See here for more information.

int PostOrderGetHeight(BinTree BT) { 
   if(BT){ 
       const int HL = PostOrderGetHeight(BT->Left); 
       const int HR = PostOrderGetHeight(BT->Right); 
       const int MaxH = (HL>HR)?HL:HR;
       return (MaxH+1); 
   } else {
       return 0;
   }
}

If one node has no further left or right nodes, this is the end of this branch and 0 is returned.

score 0 · Answer 6 · answered Aug 20 '19 at 15:16

Let's step through a tree (A) where the root has a left (B) and right (C) node, and its left node has a left node (D). All other branches are NULL.

We pass A to PostOrderGetHeight, which calls PostOrderGetHeight on its two nodes (B) and (C).

When PostOrderGetHeight is called on B, it calls PostOrderGetHeight on its left node D, and on NULL (which is its right node).

That calls PostOrderGetHeight on D, which calls PostOrderGetHeight on its two NULL nodes. Notice that calling PostOrderGetHeight on NULL return 0.

In this call PostOrderGetHeight(D), HL and HR are set to zero. So this effectively initializes them. Then MaxH is set to zero, effectively initializing it. Then the call to PostOrderGetHeight(D) returns MaxH+1 which is 1.

Remember that PostOrderGetHeight(D) was called from PostOrderGetHeight(B) so it gets this answer 1 to set HL to 1. The right branch of B is NULL, so HR gets set to 0, and MaxH gets set to 1, so PostOrderGetHeight(B) returns 2.

PostOrderGetHeight(A) called PostOrderGetHeight(B) and PostOrderGetHeight(C). Since C has two NULL branches, the call to PostOrderGetHeight(C) returns 1. This sets HL to 2 returned from PostOrderGetHeight(B) and HR to 1 returned from PostOrderGetHeight(C), making MaxH set to 2. Thus PostOrderGetHeight(A) will return 3, which is the height of tree A.

Persixty · Answer 7 · 2019-08-20T15:39:25.187

The general recursive algorithm relies on the fact that the height of a binary tree is the greater of height of its left and right sub-trees plus 1. The height of the empty tree is 0.

That's a very basic kind of recursion. The trivial case is 0 and more complex cases rely on working out the same thing for sub-parts of the problem and combining them except in the trivial case!

It's a bit like saying the height of a brick wall is the height of the wall with one brick taken off plus one, with the height of no wall being 0. OK, that's a mad way to measure walls but it's not uncommon in computing!

BinTree will be a pointer. So the line if(BT) will be false if BT is NULL (the empty tree) and the function returns a height of zero (jumping straight to else return 0).

NB: return 0; would do here. There's no need for an else because both sides of the if-statement return.

So now you look at the detail of the if-true branch.

HL = PostOrderGetHeight(BT->Left); 
HR = PostOrderGetHeight(BT->Right); 
MaxH = (HL>HR)?HL:HR;
return (MaxH+1);

HL (meaning height left) is the height of the left side of the tree from the node, HR is the height of the right side.

MaxH = (HL>HR)?HL:HR uses the ternary operator (inline if expression) that says if HL>HR the value of this expression is HL otherwise HR. That gives us our maximum height of the left and right sub-trees.

The return statement (return (MaxH+1);) adds the 1.

As stated in a comment it would be preferable to omit:

int HL,HR, MaxH;

And write

int HL = PostOrderGetHeight(BT->Left); 
int HR = PostOrderGetHeight(BT->Right); 
int MaxH = (HL>HR)?HL:HR;

Before C99 (the 1999 standard) you were required to declare all variables at the start of the function. That gave the compiler an easy ride determine how much stack was required.

But it should not be preferred style unless shackled to a compiler that imposes the rule (not even all 20th century compilers did).

It's less readable and reduce safety by risking the use of uninitialized data such as in blocks it's not used in.

Slightly more obscurely it could also stop the compiler seeing opportunities to optimize the stack layout.

But in short I wonder if this code was written for a old-school compiler or by an old-timer. I don't apologise to calling anyone an old-timer. I wrote C code on those compilers. It's not an insult.

The definition of BinTree isn't provided but it must be similar to:

typedef struct BinTree_tag;

typedef struct {
    struct BinTree_tag *Left;
    struct BinTree_tag *Right;
} *BinTree ;

What is the principle of calculating the height of binary tree by recursive method?

7 Answers7