104 Maximum Depth Of Binary Tree

---

title: Maximum Depth Of Binary Tree
tags:
- maximum-depth-of-binary-tree
- No.104
- simple
- tree
- depth-first-search
- breadth-first-search
- recurrence
- stack
- queue

---

Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

Corner Cases

• empty tree

Solutions

Post-Order Depth First Search

It's obvious that for any node a, the height of a, h(a) have:

h(a) = max{h(a.left), h(a.right)} + 1

Running time is O(V+E).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return h(root);
    }
    
    private int h(TreeNode a) {
        if (a == null) {return 0;}
        int hleft  = h(a.left);
        int hright = h(a.right);
        return (hleft > hright) ? hleft + 1 : hright + 1;
    }
}

Stack Without Recurrence

Note that we must not pop the parent untill left and right children heights are computed, which makes it a post-order dfs. Only in this case, the terms in the stack would be all the parents of the current node. And thus the depth or height is the size of the stack.

In stack post-dfs, the right child is pushed into the stack before left child so that left first right second when being poped.

Maintain the property: the current node is the first element of the stack.

Breadth First Search