Maximum Depth of Binary Tree

Q: What is the time complexity of Maximum Depth of Binary Tree?

Every approach visits each node once, so the time is O(n) . The depth-first versions use O(h) extra space for the current path, where h is the depth. The breadth-first version uses O(w) for the widest level, about half the nodes on a full tree.

Q: Should you use DFS or BFS for the maximum depth of a binary tree?

Both run in O(n) time. Depth-first search is shorter to write and uses memory in proportion to the depth, which suits wide, shallow trees. Breadth-first search counts levels directly and uses memory in proportion to the widest level, which suits deep, narrow trees. For the minimum depth, BFS wins because it can stop at the first leaf.

Q: What is the difference between the depth and the height of a binary tree?

The depth of a node counts the steps from the root down to it; the height counts the steps from it down to its deepest leaf. The maximum depth of the tree equals the height of the root. This problem counts nodes, so a single node has depth 1 ; counting edges gives one less.

EasyTree traversal

+10

You get a binary tree stored in the array tree in level order. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries. Return the maximum depth of the tree: the number of nodes on the longest path from the root down to a leaf.

Function

maxDepth(tree: integer-array) → integer

treeinteger-array: the binary tree in level order, with -1 for an empty spot
Returnsinteger: the number of nodes on the longest root-to-leaf path

Constraints

1 ≤ tree.length ≤ 32767
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 1000.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.

Examples

Input: tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Output: 4
Explanation: The longest path is 5, 8, 3, 6 (indexes 0, 1, 4, 9), which holds 4 nodes. The path through 1 stops after 2 nodes.

Input: tree = [7, -1, -1]
Output: 1
Explanation: The two -1 entries are the root's empty child spots. The root alone is a path of one node, so the depth is 1, not 0.

Input: tree = [2, -1, 9, -1, -1, -1, 4]
Output: 3
Explanation: The root 2 has no left child. Its right child 9 at index 2 has the 4 at index 6 as its right child, a path of 3 nodes.

Follow-up

How would you return the values on a longest root-to-leaf path as well as its length? If several paths tie, which one would you return?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The depth is set by the longest branch, and you cannot know which branch that is without visiting every node. So you need one full traversal that knows how deep it is at each node. Recursion, a breadth-first search by levels, and a depth-first search with your own stack each do it in one pass.

Recursion on the two subtrees

Intuition

A child spot is real when its index is inside the array and its value is not -1. The deepest path through a node goes down into its deeper subtree, so the depth at index i is 1 for the node plus the larger of the depths at 2*i+1 and 2*i+2. An empty spot has depth 0, which ends the recursion. A leaf gets 1 + max(0, 0) = 1, and the values climb back up to the root.

Each node is visited once. The call stack holds one frame per level of the current path, O(h), at most 14 here.

Algorithm

Write depth(i): if i is past the end of the array or tree[i] is -1, return 0.
Otherwise return 1 + max(depth(2*i+1), depth(2*i+2)).
Return depth(0).

def maxDepth(tree):
    def depth(i):
        # An index past the end or a -1 is an empty spot: depth 0.
        if i >= len(tree) or tree[i] == -1:
            return 0
        return 1 + max(depth(2 * i + 1), depth(2 * i + 2))

    return depth(0)

Breadth-first search, level by level

Intuition

The maximum depth is the number of levels, so you can count levels instead of following paths. A queue visits the nodes in level order. Before each batch, read the queue's size: those nodes are exactly one level, because the children you add during the batch go in behind them. Each batch adds 1 to the depth. In the first example the batches are [5], [8, 1], [3] and [6], so the answer is 4.

The queue holds one level at a time, O(w) for the widest level. On a full tree of depth 14 that is 8192 of the 16383 nodes.

Algorithm

Put the root index 0 in a queue and set depth = 0.
While the queue is not empty, add 1 to depth and read the queue's size.
Take out that many indexes. For each, queue the child indexes 2*i+1 and 2*i+2 that are inside the array and not -1.
When the queue is empty, return depth.

from collections import deque


def maxDepth(tree):
    n = len(tree)
    queue = deque([0])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):  # exactly the nodes of this level
            i = queue.popleft()
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
    return depth

Depth-first search with an explicit stack

Intuition

Keep your own stack of pairs, a node index and its depth, since nothing else remembers how far down a node is. Start with (0, 1), the root at depth 1. Every node is pushed once, carrying the length of the path that reaches it, so the largest depth you pop is the answer. In the first example the 6 is pushed as (9, 4).

The stack holds about one pending sibling per level, O(h), with no call stack to overflow. The same code works on a pointer-based tree of any depth.

Algorithm

Push (0, 1) on a stack and set best = 0.
Pop a pair (i, depth) and set best to the larger of best and depth.
For each child index 2*i+1 and 2*i+2 that is inside the array and not -1, push it with depth + 1.
Repeat until the stack is empty, then return best.

def maxDepth(tree):
    n = len(tree)
    best = 0
    stack = [(0, 1)]  # (node index, depth of that node); the root is never empty
    while stack:
        i, depth = stack.pop()
        best = max(best, depth)
        for child in (2 * i + 1, 2 * i + 2):
            if child < n and tree[child] != -1:
                stack.append((child, depth + 1))
    return best

Pitfalls and edge cases

Counting edges instead of nodes. [7, -1, -1] has depth 1, not 0.
Skipping the bounds check. In the first example the 6 at index 9 has child indexes 19 and 20, past the end of the array. Check child < n before reading tree[child].
Computing the depth from the array's length. Trailing -1 entries reach a level with no node: [7, -1, -1] has length 3 but depth 1.
Reading the queue's size inside the batch loop. Children added during the batch change it, so save it first.
Mixing up the offset in Lua and R, where arrays start at 1. Keep node indexes 0-based for 2*i+1 and read tree[i + 1].

Frequently asked questions3

What is the time complexity of Maximum Depth of Binary Tree?

Every approach visits each node once, so the time is O(n). The depth-first versions use O(h) extra space for the current path, where h is the depth. The breadth-first version uses O(w) for the widest level, about half the nodes on a full tree.

Should you use DFS or BFS for the maximum depth of a binary tree?

Both run in O(n) time. Depth-first search is shorter to write and uses memory in proportion to the depth, which suits wide, shallow trees. Breadth-first search counts levels directly and uses memory in proportion to the widest level, which suits deep, narrow trees. For the minimum depth, BFS wins because it can stop at the first leaf.

What is the difference between the depth and the height of a binary tree?

The depth of a node counts the steps from the root down to it; the height counts the steps from it down to its deepest leaf. The maximum depth of the tree equals the height of the root. This problem counts nodes, so a single node has depth 1; counting edges gives one less.

def maxDepth(tree):
    # Write code here

Test #1

Test #2

Test #3

Argument

tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]

Expected Output

Maximum Depth of Binary Tree

Function

Constraints

Examples

Hints

Solution

Recursion on the two subtrees

Breadth-first search, level by level

Depth-first search with an explicit stack

Pitfalls and edge cases

Frequently asked questions3

Similar problems