Maximum Depth Of A Binary Tree

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.

Note: A leaf is a node with no children.

Example:

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

  7
 / \
4  23
  /  \
 3    8
     / \  
    1

return it’s depth = 4.

Solution:

To find the maximum depth of a tree, we have to traverse to each and every node of a tree and find the maximum line of depth. This can be done using DFS (Depth-First Search).

In this, we will traverse from the top(root) of the tree to the bottom of the tree through each and every path of nodes. At every step we call maximum of two nodes left and right again and again till we reach at the bottom of every path. This will return the maximum depth of the tree.

If we use DFS, in the extreme cases, the overhead of the call stack might even lead to stack overflow.

A similar approach based on iteration with the help of stack data structure. Instead to call stack in the recursion, if we apply stack data structure, this idea becomes similar to that of recursion approach.

Here, we start from the root node which will be included in the stack first. Current depth will be equal to the 1. Using iteration, we will pop the current item and push the child nodes and update the value of the depth.

Implementation:

Java:

class Solution {

    public int maxDepth(TreeNode root) {
        if (root == null) {
        return 0;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> depths = new LinkedList<>();
        stack.add(root);
        depths.add(1);

        int depth = 0;
        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.pollLast();
            int currentDepth = depths.pollLast();
            if (currentNode != null) {
                depth = Math.max(depth, currentDepth);
                stack.add(currentNode.right);
                depths.add(currentDepth + 1);
                stack.add(currentNode.left);
                depths.add(currentDepth + 1);
            }
        }
        return depth;
    }
}

Complexity Analysis:

• Time Complexity: O(n).
• Space Complexity”: In the worst case, the tree will be completely unbalanced, therefore the recursion will occur n times and the space complexity will become O(n). But in average case, the height of the tree would be log(n). Therefore space complexity would be O(log(n)).