Maximum Depth of Binary Tree

Question

Given a binary tree, find its maximum depth.

The maximum depth is defined as the number of nodes along the path from the root node to the deepest leaf node.

Answer 1

public int maxDepth(TreeNode root) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if(root == null)
        return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Answer 2

I think we can use the TreeNode.val to keep the depth, and use BFS. It can be pretty straightforward. The last processed tree node contains the max depth.

public int maxDepth(TreeNode root) {        
    if (root == null) {
        return 0;
    } else {
        root.val = 1;
    }
    //BFS
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    TreeNode node = null;
    while (!queue.isEmpty()) {
        node = queue.poll();

        if (node.left != null) {
            node.left.val = node.val + 1;
            queue.offer(node.left);
        }
        if (node.right != null) {
            node.right.val = node.val + 1;
            queue.offer(node.right);
        }
    }
    return node.val;
}

Answer 3

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.

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?

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.

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

Answer 4

I used a Breadth-first Search method to solve this problem. Two queues implemented as LinkedLists in Java are maintained.

public int maxDepth(TreeNode root) {
    // Start typing your Java solution below
    // DO NOT write main() function
    LinkedList<TreeNode> trees=new LinkedList<TreeNode>();
    LinkedList<Integer> depth=new LinkedList<Integer>();
    if(root==null)
        return 0;
    trees.add(root);
    depth.add(1);
    int maxDepth=1;
    while(!trees.isEmpty())
    {
        TreeNode curr_node=trees.remove();
        int curr_depth=depth.remove();
        if(curr_depth>maxDepth)
        {
            maxDepth=curr_depth;
        }
        if(curr_node.left!=null)
        {
            trees.add(curr_node.left);
            depth.add(curr_depth+1);
        }
        if(curr_node.right!=null)
        {
            trees.add(curr_node.right);
            depth.add(curr_depth+1);
        }
    }

    return maxDepth;
}

Answer 5

public class Solution {
    Queue<TreeNode> q; Queue<Integer> q2;
    public int maxDepth(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root==null) return 0;
        q=new LinkedList<TreeNode>();
        q2=new LinkedList<Integer>();
        q.add(root);q2.add(1);
        while(!q.isEmpty()) {
            TreeNode n=q.poll();
            int level=q2.poll();
            if(n.left!=null) {
                q.add(n.left);q2.add(level+1);
            }
            if(n.right!=null) {
                q.add(n.right);q2.add(level+1);
            }
            if(q.isEmpty()) 
                return level;
        } 
        return 1;
    }
}

Answer 6

int maxDepth(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(root == NULL) return 0;
    int l = maxDepth(root->left);
    int r = maxDepth(root->right);

    if(l>r) return (l + 1);
    else return (r+1);

}

Answer 7

Breadth First Traversal with a variable control the level

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

    queue<TreeNode*> q;
    q.push(root);
    int nCnt = q.size();
    int nDepth = 0;
    while( !q.empty() )
    {
        nCnt--;
        if( nCnt == 0 )
            nDepth++;
        TreeNode* p = q.front();
        q.pop();
        if( p->left)
            q.push(p->left);
        if( p->right )
            q.push(p->right);
        if( nCnt == 0 )
            nCnt = q.size();

    }
    return nDepth;
}

Answer 8

int maxDepth(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (!root)
        return 0;
    int leftMax = maxDepth(root->left);
    int rightMax = maxDepth(root->right);
    return leftMax > rightMax ? leftMax+1 : rightMax+1;
}

Answer 9

use dfs travelsal, and record the node depth with the node point;

when visit leaf(not must) then compare the maxdepth.

    if (root == NULL) {
        return 0;
    }
    stack<pair<TreeNode*, int> > st;
    pair<TreeNode*, int> top(root, 1);
    int max_depth = 0;
    while(top.first!=NULL || !st.empty()) {
        if (top.first != NULL) {
            st.push(top);
            if (top.first->left == NULL && top.first->right == NULL) {
                //get leaf
                if (top.second > max_depth) {
                    max_depth = top.second;
                }
            }
            top.first = top.first->left;
            ++top.second;
        } else {
            top = st.top();
            st.pop();
            top.first = top.first->right;
            ++top.second;
        }   
    }
    return max_depth;

Answer 10

int maxDepth(TreeNode *root) {

    if(!root) return 0;
    else return max(1+maxDepth(root->left), 1+maxDepth(root->right));

Maximum Depth of Binary Tree

int maxDepth(TreeNode *root) {

}

Follow this question

Welcome to LeetCode

Related questions