Binary Trees and Binary Search Trees for Coding Interviews

A binary tree is made of nodes, and each node has up to two children: left and right. The top node is the root; nodes with no children are leaves. Trees show up everywhere: file systems, org charts, the DOM, and many interview questions.

A tree in computer science is drawn with the root at the top and the leaves at the bottom.

python
1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right

In these problems, trees are written as level-order arrays, read top to bottom and left to right, with null for a missing child: [3, 9, 20, null, null, 15, 7] is a root 3 with children 9 and 20, and 20 has children 15 and 7.

The tree written as [3, 9, 20, null, null, 15, 7]

Words you'll need

Depth of a node: how many edges from the root down to it (the root has depth 0).
Height of a tree: the number of levels. Some people count edges instead, so say which you mean.
Balanced: the left and right sides of every node have similar heights, so the height is about log₂ n.

Recursion fits trees naturally

Every child is the root of a smaller tree. So most tree answers look like: solve it for the left subtree, solve it for the right subtree, combine.

python

1def size(node):

2    if node is None:          # base case: an empty tree

base case: an empty tree

3        return 0

has no nodes

4    return 1 + size(node.left) + size(node.right)

this node + both subtrees

Always start from the empty tree (None) as the base case. The recursion uses O(h) call-stack space, where h is the height: O(log n) for a balanced tree, but O(n) for a tree that's just a long chain.

Tip
Trust the recursion. Assume size() already works for the children, and only think about how to combine their answers.

Depth-first vs breadth-first

Traversal	Order	Built with	Good for
Pre-order (DFS)	node, left, right	Recursion or a stack	Copying a tree, serialising it
In-order (DFS)	left, node, right	Recursion or a stack	BSTs: visits values in sorted order
Post-order (DFS)	left, right, node	Recursion or a stack	Answers that need both children first (heights, sizes)
Level-order (BFS)	level by level	A queue	Anything about levels, or the nearest node

Level-order visits one level at a time1 / 3

Level 1: 3.

Binary search trees

A binary search tree (BST) adds one rule: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. That rule makes searching like binary search:

Operation	Balanced BST	Unbalanced (worst case)
Search, insert, delete	O(log n)	O(n)
Visit all values in order	O(n)	O(n)

Searching a BST for 61 / 3

6 < 8, so it can only be in the left subtree.

Common mistakes

Missing the empty-tree base case, or treating a leaf as a special case when None children already handle it.
Checking only a node's direct children when the rule applies to whole subtrees.
Confusing depth counted in nodes with depth counted in edges: read the question.

Nice work!
You've got the big idea. Try the quick quiz below, then put it to work on the practice problems.