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; } |

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

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

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

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

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

+1See here:

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

+1The "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?

+1You 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.

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

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;

}

+1@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

-1@1337c0d3r:

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

+2according 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.

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

+1public 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;

}

+5LevelOrderTraversal, Really easy to understand, thank you!

+1great code man.

Really easy to understand.

Cudos!

0Gosh, BFS method ! Very easy to follow!

0To 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!

0As 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

+1I 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?

+1In DFS,we traverse depth wise of the tree/graph.So,all three kinds of tree traversals

pre-order:root->left->right;

in-order:left->root->right;

post-order:left->right->root;

are traversed in depth wise.

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

}

0private 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…

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

0The 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;

}

0Following 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.

+2is the condition necessary?

0is this condition

necessary?

0Pingback: [Leetcode]Maximum Depth of Binary Tree | Wei's blog

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;

}

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

0If 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

0I have a way to use queue instead of stack. It’s same way as BFS but keep track of height when move to a new level, it can also used to print nodes of each level. I have tested it, it works. If you see if has any issues, please let me know.

0if you are considering the root has height = 1 then it works perfectly.

otherwise a little modification might help.

if (currentlevelNodeCount == 0 && nextlevelcount != 0)

This will give height = 0 if the tree has only the root node.

0Pingback: LeetCode | Technical interview solutions

Pingback: LeetCode – Binary Tree : find max depth | Pursue Excellent

Pingback: [LeetCode] Maximum Depth of Binary Tree | 水中的鱼(镜像)