## 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.

1 2 3 4 5 6 | int maxHeight(BinaryTree *p) { if (!p) return 0; int left_height = maxHeight(p->left); int right_height = maxHeight(p->right); return (left_height > right_height) ? left_height + 1 : right_height + 1; } |

**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?

**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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | int maxDepthIterative(BinaryTree *root) { if (!root) return 0; stack<BinaryTree*> s; s.push(root); int maxDepth = 0; BinaryTree *prev = NULL; while (!s.empty()) { BinaryTree *curr = s.top(); if (!prev || prev->left == curr || prev->right == curr) { if (curr->left) s.push(curr->left); else if (curr->right) s.push(curr->right); } else if (curr->left == prev) { if (curr->right) s.push(curr->right); } else { s.pop(); } prev = curr; if (s.size() > maxDepth) maxDepth = s.size(); } return maxDepth; } |

1337c0d3r said on October 6, 2010

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

+8Anonymous said on October 31, 2010

why don't you use pre-order iterative traversal for computing height?

+21337c0d3r said on October 31, 2010

Yes you are right. Pre-order iterative traversal would be easier.

+31337c0d3r said on November 1, 2010

Updated: Added post-order traversal solution which does not the addition of depth field. Deleted in-order solution as pre-order would be easier.

+1spongebob said on January 4, 2011

Can you give the code of "Pre-order iterative traversal" method?

+11337c0d3r said on January 4, 2011

See here:

http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal

+1spongebob said on January 5, 2011

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?

+11337c0d3r said on January 5, 2011

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.

+1Tracy said on January 25, 2011

这个版本的非递归后序遍历是不是精简一些:

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;

}

01337c0d3r said on January 25, 2011

@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

-1Tracy said on January 26, 2011

@1337c0d3r:

OK. I'll read that post and get back to you in that thread.

+1www said on July 17, 2011

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.

+1www said on July 17, 2011

and according to your algorithm, the height of root node, will be 1

+1Shravan said on August 24, 2011

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;

}

+3Wing said on November 17, 2013

LevelOrderTraversal, Really easy to understand, thank you!

+1dznikola said on March 18, 2014

great code man.

Really easy to understand.

Cudos!

0Yunzhao said on October 17, 2011

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!

0UnderMonkey said on January 14, 2012

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

0reader said on March 26, 2012

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?

0sukkhim said on September 1, 2012

#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();

}

0naveen said on September 28, 2012

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…

0anjana said on October 10, 2012

Why can’t you just do an iterative inorder traversal and measure the size of the stack when you hit a leaf node?

0shuais said on October 29, 2012

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;

}

0Laiq Ahmed said on April 5, 2013

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.

0Xiangyu said on December 11, 2013

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;

}

0robert said on February 13, 2014

very good example code for this algorithm, Thanks for great idea.

0