Binary Tree Max Depth
Given the root node of a binary tree, write a function findMaxDepth that returns an integer corresponding to the maximum depth.
The maximum depth is going to be the node with the level furthest from the root. The root node is a 0 depth, and an empty input would be considered -1.
The tree nodes will use the following implementation:
Breakdown
Approach and test strategy
Tree height measured in edges rather than nodes
Read the approach, boundary cases, and complexity
The course counts edges: an empty tree has depth minus one, while a root with no children has depth zero. A node's depth is one plus the greater depth of its two subtrees. Choosing the empty-tree base case consistently lets leaf nodes follow the same recurrence. Do not import the node-count convention from a different problem without adjusting the contract.
Cases to check
- Check the empty tree and a lone root before larger examples.
- Use a one-sided chain to test both the returned height and recursive depth.
- Compare trees with the same number of nodes but different shapes.
Cost model
Examining every node takes O(n) time. Recursive stack space is O(h), where h can be linear for a skewed tree. An iterative traversal needs its own explicit frontier.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
This can be solved iteratively or recursively using either DFS or BFS. Follow whichever path you feel most comfortable with, but remember to mention that a recursive solution could cause a stack overflow.
All you need to track is the max depth at any point. If the current max you've found is larger than the depth of the current level, then we know to ignore this depth and continue looking. If the current depth is larger than the max we found, we store this as the new max depth.
This can be done in O(n) time and space.
Binary Tree Max Depth
Given the root node of a binary tree, write a function findMaxDepth that returns an integer corresponding to the maximum depth.
The maximum depth is going to be the node with the level furthest from the root. The root node is a 0 depth, and an empty input would be considered -1.
The tree nodes will use the following implementation: