Maximum Depth of Binary Tree
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
- 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-1or a value with0 ≤ tree[i] ≤ 1000. tree[0]is never-1, so the tree has at least one node.- The array may end with extra
-1entries 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(indexes0,1,4,9), which holds 4 nodes. The path through1stops after 2 nodes.
- Input
- tree = [7, -1, -1]
- Output
- 1
- Explanation
- The two
-1entries are the root's empty child spots. The root alone is a path of one node, so the depth is1, not0.
- Input
- tree = [2, -1, 9, -1, -1, -1, 4]
- Output
- 3
- Explanation
- The root
2has no left child. Its right child9at index2has the4at index6as its right child, a path of 3 nodes.
+13 hidden tests on Submit
Follow-up
How would you return the values on a longest root-to-leaf path, not only its length? If several paths tie, which one would you return, and how would you say so in the contract?
Hints
Open them one at a time. Each one gives away a little more.
Think about the root. If you knew the depth of its left subtree and the depth of its right subtree, what would the depth of the whole tree be?
It is
1for the root plus the larger of the two subtree depths, and an empty spot has depth0. The same rule holds at every node, so a traversal that knows how deep each node is can find the answer.Keep a stack of pairs, a node index and its depth, starting with the root at depth 1. Pop a pair, remember the largest depth seen, and push each child at
2*i+1and2*i+2that is inside the array and not-1, with the depth plus one.
Solution
The depth is set by the single longest branch, and you cannot tell which branch that is without looking at every node. So the task is a full traversal that knows how deep it is at each node. Recursion, a level by level breadth-first search, and a depth-first search with your own stack all do it in one pass; they differ in how they keep track of where they are.
Recursion on the two subtrees
Intuition
First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2. A child is real only if its index is inside the array and the value there is not -1. In [5, 8, 1, -1, 3, -1, -1, -1, -1, 6], the root 5 has children at indexes 1 and 2, the 8 at index 1 has an empty left spot at 3 and the 3 at index 4 on its right, and that 3 has the 6 at index 9 below it.
Now the idea. The deepest path through a node goes down into whichever of its two subtrees is deeper. So the depth of the subtree at index i is 1 for the node itself 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.
Every node is visited once, so the time is O(n). The call stack holds one frame per level of the current path, O(h) where h is the depth, at most 14 here. That limit is what makes recursion safe in this problem. On a pointer-based tree shaped like a long chain, the same code would hit the recursion limit, which is 1000 frames in Python.
Algorithm
- Write
depth(i): ifiis past the end of the array ortree[i]is-1, return0. - 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 in the tree, so you can count levels instead of following paths. A queue visits the nodes in level order: start it with the root, and every time you take a node out, add its real children at the back.
To count levels, process the queue in batches. Before each batch, read how many nodes the queue holds. Those are exactly the nodes of one level, because the children you add during the batch go in behind them. Take out that many nodes, queue their children, and add 1 to the depth. When the queue is empty, the depth is the number of batches. In the first example the batches are [5], [8, 1], [3] and [6], so the answer is 4.
Every node enters and leaves the queue once, O(n) time. The queue holds one level at a time, O(w) space for the widest level w. On a full tree the bottom level holds about half the nodes, 8192 of the 16383 at depth 14.
Algorithm
- Put the root index
0in a queue and setdepth = 0. - While the queue is not empty, add
1todepthand read the queue's size. - Take out that many indexes. For each, queue the child indexes
2*i+1and2*i+2that 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 depthDepth-first search with an explicit stack
Intuition
You can follow paths, as the recursion does, without making a single recursive call. Keep your own stack, and store each node together with its depth, since nothing else remembers how far down it is. Start with the pair (0, 1): the root, at depth 1.
Pop a pair, compare its depth with the best seen so far, and push each real child with depth + 1. Every node in the tree is pushed exactly 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 at index 9 is pushed as (9, 4), and no pair goes deeper.
The time is O(n). The stack holds the pending siblings along the current path, at most about one per level, so the space is O(h), the same as the recursion but with no call stack to overflow. This is the version to reach for when a tree can be deep, and it carries over unchanged to pointer-based trees.
Algorithm
- Push
(0, 1)on a stack and setbest = 0. - Pop a pair
(i, depth)and setbestto the larger ofbestanddepth. - For each child index
2*i+1and2*i+2that is inside the array and not-1, push it withdepth + 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
Most wrong answers on this problem are off by one, or come from treating an empty spot as a node.
- Counting edges instead of nodes. A single node has depth
1here; returning0for it, or3for a 4-node path, is one short. - Skipping the bounds check. A leaf near the end of the array can have child indexes past its last entry, because the array may stop right after the last node. Check
child < nbefore readingtree[child]. - Reading the depth off the array's length. The array may carry extra
-1entries at the end, so its length can belong to a deeper level than any real node. - Treating
-1as a value. It marks a missing node, so it must not be pushed, queued or counted. - Assuming the tree is balanced. The answer follows the longest branch, as in a left chain of 14 nodes where every right spot is empty.
- Reading the queue size inside the loop in the breadth-first version. The size changes as children are added, so save it before the batch starts.
- Mixing up the offset in Lua and R, where arrays start at 1. Keep the node indexes 0-based for the
2*i+1arithmetic and readtree[i + 1].
Frequently asked questions4
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 path being explored, where h is the depth. The breadth-first version uses O(w) for the widest level, which can be about half the nodes on a full tree.
Should you use DFS or BFS for the maximum depth of a binary tree?
Both give the right answer 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 has the edge, because it can stop at the first leaf it meets.
How do you find the maximum depth of a binary tree without recursion?
Use an explicit stack of pairs: a node and its depth. Start with the root at depth 1, pop a pair, record its depth, and push each child with the depth plus one. The largest depth you pop is the answer. A queue processed one level at a time also works, counting one per level.
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, and the height of a node counts the steps from it down to its deepest leaf. The maximum depth of the tree and the height of the root are the same number. This problem counts nodes, so a single node has depth 1; some books count edges instead, which gives one less.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def maxDepth(tree):
# Write code hereCase 1
Case 2
Case 3
Input
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Expected
4