Back to Topics
Tree
A tree is a connected, acyclic graph with a designated root. Binary trees (at most 2 children) are the most common interview topic. Binary Search Trees (BSTs) maintain the invariant left < node < right, enabling O(log n) operations on balanced trees. DFS and BFS are the two fundamental traversal strategies.
Key Ideas
- A tree with n nodes has exactly n−1 edges
- Height of a balanced binary tree is O(log n); degenerate (skewed) tree is O(n)
- DFS traversals: pre-order (root, left, right), in-order (left, root, right), post-order (left, right, root)
- In-order traversal of a BST visits nodes in sorted ascending order
- Recursive DFS is natural for trees; iterative uses an explicit stack
- Many tree problems follow: base case (null) → recurse left → recurse right → combine
Complexity
| Operation | Time | Space |
|---|---|---|
| Access / Search (balanced BST) | O(log n) | O(log n) |
| Access / Search (skewed BST) | O(n) | O(n) |
| Insert (balanced BST) | O(log n) | O(log n) |
| Delete (balanced BST) | O(log n) | O(log n) |
| Level-order traversal (BFS) | O(n) | O(n) |
Common Patterns
DFS — Top-downPass information from parent to children (e.g. current path sum, min/max seen so far).
DFS — Bottom-upCombine results from children before returning to parent (e.g. height, diameter).
BFS / Level-orderProcess nodes level by level using a queue — useful for level-specific aggregations.
BST PropertiesUse the BST invariant to prune half the tree at each step; validate by passing min/max bounds.
Code Example
Max depth — bottom-up DFSpython
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root: TreeNode | None) -> int:
if root is None:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)💡
Draw the recursion tree before coding. If you can define the return value from a subtree, bottom-up DFS usually gives the cleanest solution.