Maximum Depth of Binary Tree
EasyTrees
Given the root of a binary 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.
On this page a tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: root = [4, 2, 7, null, null, 5, 9, null, 6] Output: 4
The longest path is 4 → 7 → 5 → 6, four nodes.
Input: root = [3, null, 8] Output: 2
The root and its one child, 8, on the right.
Constraints
- The tree has 0 to 10⁴ nodes.
-100 ≤ node.val ≤ 100
Stuck?
Hint 1
A tree is one level deeper than the deeper of its two subtrees.
Hint 2
Recurse, with an empty tree as the base case at depth 0. Or count the levels with a queue, one level at a time.
The idea
The depth of a tree is one node, the root, plus the depth of its deeper subtree. An empty tree has depth 0, which gives the recursion its place to stop.
Time O(n)Extra space O(h) for a tree of height h
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 3
An empty tree has no nodes, so its depth is 0. Both children of a leaf are empty, so a leaf comes out as 1 + 0, which is 1, as it should.
function maxDepth(root) { if (!root) return 0; const left = maxDepth(root.left); const right = maxDepth(root.right); return 1 + Math.max(left, right);}The trap
Returning 0 for a leaf counts the edges on the longest path instead of the nodes. The recursion has the same shape as the right one, so it reads as correct, but every answer comes out one short. Any tree with at least one node shows it, a lone node most plainly.
function maxDepth(root) { // counts the edges, not the nodes: a lone leaf comes out as 0 if (!root || (!root.left && !root.right)) return 0; const left = maxDepth(root.left); const right = maxDepth(root.right); return 1 + Math.max(left, right);}