Skip to main content

Maximum Depth of Binary Tree Solution

Problem Description​

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Examples​

Example 1:

Input Tree

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints​

  • The number of nodes in the tree is in the range [0, 104].
  • -100 <= Node.val <= 100

Solution for Maximum Depth of Binary Tree Problem​

Breadth-First Search (BFS) Approach​

Intuition​

Another approach to find the maximum depth of a binary tree is to use breadth-first search (BFS). We start from the root node and traverse the tree level by level, incrementing the depth at each level until we reach the deepest leaf node.

Approach​

  1. Initialize a queue and push the root node into it.
  2. Initialize a variable depth to store the maximum depth, initially set to 0.
  3. Perform BFS traversal:
    • Increment depth for each level visited.
    • Push all the children of the current level into the queue.
  4. Return depth after traversing all levels.

Implementation​

Live Editor
function MaxDepthOfBinaryTree() {
  class TreeNode {
    constructor(val) {
      this.val = val;
      this.left = null;
      this.right = null;
    }
  }

  // Creating the binary tree
  const root = new TreeNode(3);
  root.left = new TreeNode(9);
  root.right = new TreeNode(20);
  root.right.left = new TreeNode(15);
  root.right.right = new TreeNode(7);

  const maxDepth = function (root) {
    if (!root) return 0;

    let depth = 0;
    const queue = [root];

    while (queue.length) {
      const size = queue.length;
      for (let i = 0; i < size; i++) {
        const node = queue.shift();
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
      }
      depth++;
    }

    return depth;
  };

  const result = maxDepth(root);
  return (
    <div>
      <p>
        <b>Binary Tree:</b> {JSON.stringify(root)}
      </p>
      <p>
        <b>Maximum Depth:</b> {result}
      </p>
    </div>
  );
}
Result
Loading...

Code in Different Languages​

Written by @Vipullakum007
 function maxDepth(root) {
 if (!root) return 0;

 let depth = 0;
 const queue = [root];

 while (queue.length) {
     depth++;
     const levelSize = queue.length;
     for (let i = 0; i < levelSize; ++i) {
     const node = queue.shift();
     if (node.left) queue.push(node.left);
     if (node.right) queue.push(node.right);
     }
 }

 return depth;
 }

Complexity Analysis​

  • Time complexity: O(n), where n is the number of nodes in the tree. We visit each node once.
  • Space complexity: O(w), where w is the maximum width of the tree (i.e., the number of nodes at the maximum level). In the worst case, the maximum width could be n/2 in a complete binary tree, so the space complexity is O(n).

References​