trees · Problem 3 of 3
Maximum Depth of a Tree
medium
Amazon
Meta
AmazonMetaA node is { value, left, right }, with null for a missing child. Return the number of nodes on the longest root-to-leaf path.
maxDepth({ value: 1, left: null, right: null }) -> 1Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| maxDepth(null) | empty | 0 | — |
| maxDepth({"value":1,"left":null,"right":null}) | single node | 1 | — |
| maxDepth({"value":1,"left":{"value":2,"left":{"value":3,"left":null,"right":null},"right":null},"right":null}) | left heavy | 3 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(h) for height h
Every node is visited once. The space is the recursion stack, which is the tree's height — O(n) for a degenerate tree, O(log n) for a balanced one.
Hints
Stuck? Hints open one at a time, each giving a little more away.
2 hints left