Deepest Level Count
Problem
Given the root of a binary tree, return the number of levels on the longest path from the root down to any leaf. A tree with only a root counts as one level, and an empty tree counts as zero.
Examples
Input: tree = 3 with children 9 and 20, where 20 has children 15 and 7
Output: 3
Why: the path 3, 20, 15 covers three levelsInput: tree = 1 with a right child 2, whose right child is 3
Output: 3
Why: a completely lopsided tree still counts every levelInput: tree = empty
Output: 0
Why: edge case, there are no levels to countHints
0 / 3
The depth of a tree is decided entirely by its two subtrees, which are themselves trees. That self-similarity is the whole solution.
Define the answer for a node in terms of the answers for its children, and pick a base case for the missing child that makes the arithmetic work.
For an absent node, report zero levels. For any real node, ask both children for their depths, take the larger one, and add one for the level the node itself occupies.
Solution
Depth is defined recursively: an absent node contributes zero levels, and a present node contributes one more than the deeper of its two subtrees. That single rule handles balanced and lopsided trees identically, with no special case beyond the empty child. Every node is visited exactly once. Time is O(n), and space is O(h) for the call stack, where h is the height of the tree.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def depth(node):
if node is None: return 0 # an absent branch adds no level
# a node sits exactly one level above its deeper subtree
return 1 + max(depth(node.left), depth(node.right))
print(depth(T(3, T(9), T(20, T(15), T(7))))) # -> 3
print(depth(T(1, None, T(2, None, T(3))))) # -> 3
print(depth(None)) # -> 0Stuck on the idea rather than the code? Tree Depth and Balance covers it.