You are given root, the root of a binary tree (or nothing, for an empty tree).
Return its depth: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0, and a tree with only a root has depth 1.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [6, 2, 8, 1, null, 7, 9, null, null, 5]
- Output
- 4
Example 2
- Input
- root = [1, null, 2]
- Output
- 2
Constraints
- The tree holds 0 to 1000 nodes.
- Every value is between −100 and 100.
Show the pattern
Trees
A tree's depth is one more than the deeper of its two subtrees' depths. Each node's answer comes straight from its children's answers: recursion.
See trees in a visualiserShow the approach
Recurse. An empty tree has depth 0. Otherwise the depth is 1 + max(depth(left), depth(right)):
the root, plus the deeper of its two subtrees. Each node is visited once.
Going level by level with a queue and counting the levels gives the same answer without recursion.
Time: O(n) · Space: O(h) for the recursion, h the tree's height