Solutions

1. Depth First Search

O(n) time | O(h) space, for a tree of height h

Intuition

We can traverse through the tree with DFS, keeping the depth of the deepest node we reach.

Algorithm

Return 0 when the node is null.
Ask the left and right subtrees for their depths.
Return 1 plus the greater depth of the child subtrees.

depth 1: visit 3

1 / 8

Code

Recursive implementation

Code

# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {number}
 */
var maxDepth = function (root) {
  if (!root) return 0
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
}

// Definitions:
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//
//     TreeNode() {}
//
//     TreeNode(int val) {
//         this.val = val;
//     }
//
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

Iterative implementation

Code

# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    deepest = 0
    stack = [(root, 1)]
    while stack:
        node, depth = stack.pop()
        deepest = max(deepest, depth)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return deepest

// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {number}
 */
var maxDepth = function (root) {
  if (!root) return 0
  let deepest = 0
  const stack = [[root, 1]]
  while (stack.length > 0) {
    const [node, depth] = stack.pop()
    deepest = Math.max(deepest, depth)
    if (node.left) stack.push([node.left, depth + 1])
    if (node.right) stack.push([node.right, depth + 1])
  }
  return deepest
}

// Definitions:
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//
//     TreeNode() {}
//
//     TreeNode(int val) {
//         this.val = val;
//     }
//
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int deepest = 0;
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> depths = new ArrayDeque<>();
        nodes.push(root);
        depths.push(1);
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int depth = depths.pop();
            deepest = Math.max(deepest, depth);
            if (node.left != null) {
                nodes.push(node.left);
                depths.push(depth + 1);
            }
            if (node.right != null) {
                nodes.push(node.right);
                depths.push(depth + 1);
            }
        }
        return deepest;
    }
}

2. Breadth First Search

O(n) time | O(n) space

Intuition

We can traverse through the tree with BFS, level by level, so the maximum depth is the number of levels passed.

Algorithm

Return 0 when the root is null.
Create a depth of 0 and a currentDepthQueue holding the root.
Traverse through the tree while the currentDepthQueue is not empty.
- Increase depth by one.
- Collect the children of every node in the currentDepthQueue into a nextDepthQueue.
- Make the nextDepthQueue the currentDepthQueue.
Return the depth.

depth 1: take 3

1 / 8

Code

# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    depth = 0
    currentDepthQueue = [root]
    while currentDepthQueue:
        depth += 1
        nextDepthQueue = []
        for node in currentDepthQueue:
            if node.left:
                nextDepthQueue.append(node.left)
            if node.right:
                nextDepthQueue.append(node.right)
        currentDepthQueue = nextDepthQueue
    return depth

// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {number}
 */
var maxDepth = function (root) {
  if (!root) return 0
  let depth = 0
  let currentDepthQueue = [root]
  while (currentDepthQueue.length > 0) {
    depth += 1
    const nextDepthQueue = []
    for (const node of currentDepthQueue) {
      if (node.left) nextDepthQueue.push(node.left)
      if (node.right) nextDepthQueue.push(node.right)
    }
    currentDepthQueue = nextDepthQueue
  }
  return depth
}

// Definitions:
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//
//     TreeNode() {}
//
//     TreeNode(int val) {
//         this.val = val;
//     }
//
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int depth = 0;
        List<TreeNode> currentDepthQueue = new ArrayList<>();
        currentDepthQueue.add(root);
        while (!currentDepthQueue.isEmpty()) {
            depth++;
            List<TreeNode> nextDepthQueue = new ArrayList<>();
            for (TreeNode node : currentDepthQueue) {
                if (node.left != null) nextDepthQueue.add(node.left);
                if (node.right != null) nextDepthQueue.add(node.right);
            }
            currentDepthQueue = nextDepthQueue;
        }
        return depth;
    }
}