Maximum Height (Depth) of a Binary Tree

April 21, 2010 in binary tree

Given a binary tree, find its maximum height.


The maximum height of a binary tree is defined as the number of nodes along the path from the root node to the deepest leaf node. Note that the maximum height of an empty tree is 0.

Recursive Solution:
We can solve this easily using recursion. Why? Because each of the leftChild and rightChild of a node is a sub-tree itself. We first compute the max height of left sub-tree, then compute the max height of right sub-tree. Therefore, the max height of the current node is the greater of the two max heights + 1. For the base case, the current node is NULL, we return zero. NULL signifies there is no tree, therefore its max height is zero.

Further Thoughts:
The recursive solution is pretty neat, right? Here’s a challenge: How about finding an iterative solution for maxHeight()? How would you approach this problem?

Binary-tree visualization of the Yahoo search engine bot crawling the experimental website. The total number of nodes grow with an exponential rate as the tree deepens. The animated version showing the tree growing over the year can be found here (Warning: large file size, 13MB).

Hint:
Read my post: Binary Search Tree In-Order Traversal Iterative Solution. This should give you enough hints to get started.

Iterative Solution:
We could apply the same in-order traversal of a BST in the binary tree. By saying “in-order” traversal I mean traversing the tree such that it reaches the leaf first (deepest). In other words, we are doing a Depth-first Search (DFS). In fact, all three kinds of tree traversal (pre-order, in-order, and post-order) are doing DFS. Therefore, we could modify any existing iterative solution of tree traversals to solve this problem.

As pre-order and in-order iterative traversals are easier to implement, your best bet is to code either one of them during an interview session. As we traverse the tree, we would keep track of the current depth and record each node’s depth, so that we know which depth we are in when we return to the node at a later time. (In pre-order or in-order traversals, it might return several levels above the current level when a node is popped off the stack).

On the other hand, post-order traversal guarantees to return exactly one level above a node that is popped off the stack. Therefore, we could devise a solution utilizing post-order traversal without modifying the existing tree structure. We keep track of the current depth and update the maximum depth as we traverse the tree.

Another solution is to utilize Breadth-first Search (BFS). Unlike DFS, we traverse the tree level by level, thus we are able to obtain the max depth in a direct manner. Read my post: Printing a Binary Tree in Level Order for more information.

Below is the code for finding the maximum depth of a binary tree using post-order traversal, without recursion.

VN:F [1.9.22_1171]
Rating: 4.0/5 (42 votes cast)
Maximum Height (Depth) of a Binary Tree, 4.0 out of 5 based on 42 ratings

27 responses to Maximum Height (Depth) of a Binary Tree

  1. Updated: Iterative solution of finding the maximum height of a binary tree.

    VA:F [1.9.22_1171]
    +8
  2. why don't you use pre-order iterative traversal for computing height?

    VA:F [1.9.22_1171]
    +2
  3. Yes you are right. Pre-order iterative traversal would be easier.

    VA:F [1.9.22_1171]
    +3
  4. Updated: Added post-order traversal solution which does not the addition of depth field. Deleted in-order solution as pre-order would be easier.

    VA:F [1.9.22_1171]
    +1
  5. Can you give the code of "Pre-order iterative traversal" method?

    VA:F [1.9.22_1171]
    +1
  6. The "Pre-order iterative" way will push both left and right sub-trees into the stack. So counting the stack size will definitely not work. How do you calculate the depth?

    VA:F [1.9.22_1171]
    +1
  7. You would need to modify the tree structure to add a 'depth' field. When you push a node, you would need to set the depth field too.

    Therefore, when you pop off a node later, you would get the new depth too by reading the depth field.

    VA:F [1.9.22_1171]
    +1
  8. 这个版本的非递归后序遍历是不是精简一些:

    int maxHeightNoR(Node *root)
    {
    stack s;
    const Node* itr = root;
    int h = 0;
    int maxH = 0;

    while (itr || !s.empty())
    {
    if (!itr)
    {
    while (!s.empty() && itr == s.top()->right)
    {
    itr = s.top();
    s.pop();
    h–;
    }

    itr = s.empty() ? NULL : s.top()->right;
    }
    else
    {
    s.push(itr);
    h++;
    if (h > maxH)
    maxH = h;

    itr = itr->left;
    }
    }
    return maxH;
    }

    VA:F [1.9.22_1171]
    +1
  9. @Tracy:
    Are you sure you are able to do postorder traversal iterative using a single stack? Please see here: http://www.ihas1337code.com/2010/10/binary-tree-post-order-traversal.html

    I have the two-stack solution, but I have yet to see a one-stack solution for post-order traversal. Please enlighten me ;)

    VA:F [1.9.22_1171]
    -1
  10. @1337c0d3r:
    OK. I'll read that post and get back to you in that thread.

    VA:F [1.9.22_1171]
    +2
  11. according to http://en.wikipedia.org/wiki/Binary_tree.The definition of tree height is diff than what you mentioned “Note that the maximum height of an empty tree is 0.”

    “The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.”
    “The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.”

    Basically, it means at the root node, the depth is 0.

    VA:F [1.9.22_1171]
    +1
  12. and according to your algorithm, the height of root node, will be 1

    VA:F [1.9.22_1171]
    +1
  13. public int heightIterative() {
    Queue q = new LinkedList();
    BTreeNode node;
    int currentLevelNodes, nextLevelNodes,depth;
    if (root == null)
    return 0;
    q.add(root);
    currentLevelNodes = 1;depth=0;
    nextLevelNodes = 0;
    while (!q.isEmpty()) {
    node = q.remove();
    currentLevelNodes–;
    if (node.left != null) {
    q.add(node.left);
    nextLevelNodes++;
    }
    if (node.right != null) {
    q.add(node.right);
    nextLevelNodes++;
    }
    if (currentLevelNodes == 0) {
    depth++;
    currentLevelNodes = nextLevelNodes;
    nextLevelNodes = 0;
    }
    }
    return depth;
    }

    VA:F [1.9.22_1171]
    +3
  14. To calculate the maxHight via pre-order/in-order iterative traversal, is it necessary for each node to add an additional data field to record its level?

    Thanks in advance!

    VA:F [1.9.22_1171]
    0
    • As spongebob pointed out:
      “The “Pre-order iterative” way will push both left and right sub-trees into the stack. So counting the stack size will definitely not work. How do you calculate the depth?”
      Though I believe there’s a simple walk-around based on the pre/in-order traversal:
      if(cur->left ^ cur->right) depth++; //increment the depth when only 1 of the children is true

      VN:F [1.9.22_1171]
      0
  15. I don’t undestand the statement “all three kinds of tree traversal (pre-order, in-order, and post-order) are doing DFS”. Why is pre-order traversal DFS? Could you please explain?

    VA:F [1.9.22_1171]
    0
  16. #include
    #include
    #include”malloc.h”

    struct node
    {
    int data;
    struct node* left;
    struct node* right;
    };
    int size(struct node* n)
    {
    if(n==NULL)
    return 0;
    else
    return (size(n->left)+1+size(n->right));
    }
    int maxdepth(struct node* n)
    {
    int ldepth,rdepth;
    if(n==NULL)
    {
    return 0;
    }
    else
    {
    ldepth=maxdepth(n->left);
    rdepth=maxdepth(n->right);
    if(ldepth>rdepth)
    return (ldepth+1);
    else
    return (rdepth+1);
    }
    }
    int lookup(struct node* node,int target)
    {
    if(node==NULL)
    return 0;
    else if(target==node->data)
    return 1;
    else if(targetdata)
    return(lookup(node->left,target));
    else
    return(lookup(node->right,target));
    }
    struct node* newnode(int data)
    {
    struct node* newnod=(struct node*)malloc(sizeof(struct node));
    newnod->data=data;
    newnod->left=NULL;
    newnod->right=NULL;
    return newnod;
    }
    struct node* insert(struct node* root,int target)
    {
    if(root==NULL)
    return(newnode(target));
    else if(targetdata)root->left=insert(root->left,target);
    else root->right=insert(root->right,target);
    return root;
    }

    void main()
    {
    int result,s,max;
    struct node* newnode=NULL;
    clrscr();
    newnode=insert(newnode,2);
    newnode=insert(newnode,3);
    newnode=insert(newnode,4);
    max=maxdepth(newnode);
    printf(“maxdepth %d\n”,max);
    s=size(newnode);
    result=lookup(newnode,3);
    printf(“size %d\n”,s);
    printf(“%d”,result);
    getch();
    }

    VA:F [1.9.22_1171]
    0
  17. private int height;
    public void Height(node n){

    if(n!=null && n.getLeft()==null && n.getRight()==null){

    int H = getH(n);
    if(H>this.height) height = H;
    }
    if(n==null) return;
    else {
    Height(n.getLeft());
    Height(n.getRight());
    }

    }
    public int getH(node n){
    int temp = 0;
    while(n.getParent()!=null){
    temp++;
    n =n.getParent();
    }
    return temp;
    }
    public int getHeight(){

    Height(this.getRoot());

    return height+1;
    }

    // soln with bad complexity…

    VA:F [1.9.22_1171]
    0
  18. Why can’t you just do an iterative inorder traversal and measure the size of the stack when you hit a leaf node?

    VA:F [1.9.22_1171]
    0
    • The author has stated that reason in the post, and I’ve also tried in order, it just doesn’t work, you can’t track the height easily by a counter or the size of the stack. Do it and you’ll know.

      I have a post order version that passes the judge, it’s simpler than the version in the post so I’d like to share. Let me know if you got question or find out my code is wrong.

      int maxDepth(TreeNode *root) {
      // Start typing your C/C++ solution below
      // DO NOT write int main() function
      int height = 0;
      vector stack;
      TreeNode* previous = NULL;

      while (root || stack.size())
      {
      if (root)
      {
      stack.push_back(root);
      root = root->left;
      if (stack.size() > height)
      height = stack.size();
      continue;
      }

      if (stack.back()->right == NULL || previous == stack.back()->right)
      {
      previous = stack.back();
      stack.pop_back();
      }
      else
      root = stack.back()->right;
      }

      return height;
      }

      VA:F [1.9.22_1171]
      0
  19. Following is a little easy to understand version of iterative post order traversal, calculating the height. I tried to keep the logic simple as possible.

    Feel free to ask question if anything wrong with the code.

    VA:F [1.9.22_1171]
    +1
  20. public static int getMaximumHeightI(Node root) {
    if (root == null)
    return 0;
    Node current = root;
    int level=0;
    int maxLevel=0;
    Stack stack = new Stack();
    while (current != null || !stack.isEmpty()) {
    if (current != null) {
    stack.push(current);
    current = current.left;
    } else {
    current = stack.pop();
    level–;
    if(level>maxLevel)
    maxLevel=level;
    current = current.right;
    }
    level++;
    }
    return maxLevel;
    }

    VA:F [1.9.22_1171]
    -1
  21. very good example code for this algorithm, Thanks for great idea.

    VA:F [1.9.22_1171]
    0
  22. If the tree is empty, return -1.
    Compute the depth of subtrees recursively.
    Compare the height in the left and right subtree – return the maximum one.

    For code and explanation http://www.algoqueue.com/algoqueue/default/view/8454144/compute-height-of-a-tree-at-root

    VA:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.