Complexity Analysis
def tree_height(node):
if node is None:
return 0
left = tree_height(node.left)
right = tree_height(node.right)
return 1 + max(left, right)What is the time and space complexity?
Work it out before scrolling down.
Time
O(n)
Space
O(h)
How to derive it
Visits every node exactly once → O(n) time where n is the number of nodes. Space is the recursion depth, which equals the tree height h. For a balanced tree h = O(log n); for a skewed tree h = O(n). When the answer depends on tree shape, express it as O(h).