Traverse trees recursively
Solve binary tree problems by combining answers from subtrees.
- Write recursive tree functions with a clear base case.
- Compare pre-order, in-order, post-order, and level-order traversal.
- Use the binary search tree property.
A binary tree node has a value and up to two children. Most tree problems have the same shape: handle the empty tree (the base case), solve the problem for the left and right subtrees recursively, then combine the answers. The height of the tree, whether two trees are identical, the sum of a path - all follow this pattern.
Traversals and the BST property
- Pre-order (node, left, right): copying or serializing a tree.
- In-order (left, node, right): visits a binary search tree in sorted order.
- Post-order (left, right, node): when a node needs its children’s answers first, like height.
- Level-order (breadth-first, with a queue): processing the tree one depth at a time.
In a binary search tree (BST), every value in a node’s left subtree is smaller and every value in its right subtree is larger, so search, insert, and delete take O(h), where h is the height.
1class TreeNode:
2 def __init__(self, value, left=None, right=None):
3 self.value = value
4 self.left = left
5 self.right = right
6
7def max_depth(node):
8 if node is None:
9 return 0
10 return 1 + max(max_depth(node.left), max_depth(node.right))
11
12# 3
13# / \
14# 9 20
15# / \
16# 15 7
17root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
18print(max_depth(root))3
Recursive tree solutions visit every node once, so they are O(n) time. Their space is O(h) for the call stack: O(log n) for a balanced tree, but O(n) for a tree that degenerates into a line. If the interviewer worries about deep recursion, convert to an explicit stack or a BFS queue.
Key takeaways
Base case for empty trees, recurse on children, combine.
In-order traversal of a BST is sorted.
Recursion uses O(h) stack space.
Lesson quiz
5 questions · pass with 4 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: solve interview problems
Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.
Measure a tree’s depth
Read a binary tree in level order, with null for missing children (for example 3 9 20 null null 15 7). The starter code builds the tree. Print its maximum depth; an empty line means an empty tree with depth 0.
- Example tree
- Left-leaning
- Empty tree
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…