Maximum Depth of Binary Tree

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.

Example: Given a binary tree

    3 -------------- Depth : 1
   /  \
  5    6 ----------- Depth : 2
      /  \
     2    7 -------- Depth : 3

Depth = 3

First of all, here is the definition of the TreeNode which we would use.

/* Definition for a binary tree node. */
public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

By definition, the maximum depth of a binary tree is the maximum number of steps to reach a leaf node from the root node.

Depth Of a Binary Tree

Recursive Solution

class Solution {
  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    } else {
      int left_height = maxDepth(root.left);
      int right_height = maxDepth(root.right);
      return Math.max(left_height, right_height) + 1;
    }
  }
}
  • Time Complexity: We visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes.
  • Space Complexity: In the worst case, the tree is completely unbalanced, e.g. each node has only left child node, the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be O(N). But in the best case (the tree is completely balanced), the height of the tree would be log(N). Therefore, the space complexity, in this case, would be O(log(N)).

Iterative Solution

We could also convert the above recursion into an iteration, with the help of the Queue data structure. The idea is to keep the next nodes to visit in a Queue. And calculate the height of the tree by another Queue.

class Solution {
  
  public int maxDepth(TreeNode root) {

    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    Queue<Integer> depths = new LinkedList<>();
    queue.offer(root);
    depths.offer(1);
    int depth = 0;
    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      int curDepth = depths.poll();
      depth = Math.max(curDepth, depth);
      if (node.left != null) {
        queue.offer(node.left);
        depths.offer(curDepth + 1);
      }
      if (node.right != null) {
        queue.offer(node.right);
        depths.offer(curDepth + 1);
      }
    }
    return depth;
  }
}
  • Time Complexity: O(N).
  • Space Complexity: In the worst case, the tree is completely unbalanced, e.g. each node has an only left child node, the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be O(N). But in the average case (the tree is balanced), the height of the tree would be log(N). Therefore, the space complexity, in this case, would be O(log(N)).

Categories: Binary Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s