Tree interview patterns

Trees are the most common interview topic, and nearly every tree problem is one of four shapes: return a value up (diameter, balanced, LCA), pass state down (good nodes, path sums), go level by level (right side view, zigzag), or use BST order (k-th smallest). Plus rebuilding a tree from two traversals and prefix sums on a path.

Pick the shape first#

Drawing diagram…

Shape 1: bottom-up, return a value and keep a best#

The function returns what the parent needs. That is often different from the final answer, which is kept in an outer variable. Diameter is the classic example: the longest path can bend at any node, using a branch on each side, but a parent can only extend one branch. So each node returns its height, and records left + right as a candidate answer.

Run the trace

diameter_trace.go

package main
 
import (
	"fmt"
	"strings"
)
 
type Node struct {
	Val         int
	Left, Right *Node
}
 
// diameter: each call returns its height up to the parent and updates the best path through itself.
func diameter(root *Node) int {
	best := 0
	var height func(n *Node, depth int) int
	height = func(n *Node, depth int) int {
		if n == nil {
			return 0
		}
		l := height(n.Left, depth+1)
		r := height(n.Right, depth+1)
		best = max(best, l+r)
		fmt.Printf("%snode %d: left=%d right=%d path through=%d return %d\n", strings.Repeat("  ", depth), n.Val, l, r, l+r, 1+max(l, r))
		return 1 + max(l, r)
	}
	height(root, 0)
	return best
}
 
func main() {
	//       1
	//      / \
	//     2   3
	//    / \
	//   4   5
	root := &Node{1, &Node{2, &Node{Val: 4}, &Node{Val: 5}}, &Node{Val: 3}}
	fmt.Println("diameter:", diameter(root))
}

Output

    node 4: left=0 right=0 path through=0 return 1
    node 5: left=0 right=0 path through=0 return 1
  node 2: left=1 right=1 path through=2 return 2
  node 3: left=0 right=0 path through=0 return 1
node 1: left=2 right=1 path through=3 return 3
diameter: 3

Children finish before their parent (post-order), which is why the deepest nodes print first. The same shape solves:

Balanced tree: return the height, or −1 as soon as any subtree is unbalanced, so a single pass suffices instead of O(n²).
Maximum path sum: return val + max(0, best child); record val + left + right.
Lowest common ancestor: return the target node if you are standing on one, otherwise whatever your children found. The first node with a result from both sides is the LCA.

Shape 2: top-down, pass state to the children#

When the answer at a node depends on its ancestors (the path from the root), pass that state as parameters. Count Good Nodes passes the maximum value seen so far. Path Sum II passes the remaining sum and keeps the current path in a shared slice, which is exactly backtracking: append on the way in, remove on the way out, and clone the path when saving it.

Prefix sums on a tree path

Path Sum III counts paths that go downward but may start and end at any node. Along one root-to-node path, this is the array problem "subarrays that sum to k" from Arrays & prefix sums: keep a map of the prefix sums on the current path, and at each node add seen[sum − target]. The tree adds one rule: decrement the count when you leave a node, because a sibling branch must not see prefixes that aren't its ancestors.

Shape 3: level by level#

For anything about depth or rows (right side view, zigzag, level averages, connecting next pointers), process one level per loop iteration: take the whole current level, build the next one from its children, and swap. Holding the level in its own slice tells you where each row starts and ends, which a single queue does not.

Shape 4: BST order#

A BST's in-order traversal is sorted. K-th smallest, validating a BST, finding the successor, and "convert to a sorted list" all reduce to an in-order walk. The iterative version with an explicit stack lets you stop early after k nodes, without walking the rest of the tree:

for {
	for n != nil { // go as far left as possible
		stack = append(stack, n)
		n = n.Left
	}
	n = stack[len(stack)-1] // the next smallest
	stack = stack[:len(stack)-1]
	// visit n here
	n = n.Right
}

Rebuilding a tree from two traversals#

Preorder lists the root first, then its left subtree, then its right subtree. Inorder puts the root between its subtrees. So take the next preorder value as the root, find its position in inorder, and everything to its left in inorder is the left subtree. A map from value to inorder index makes each step O(1), so the whole rebuild is O(n).

preorder	inorder	root	left (inorder)	right (inorder)
3 9 20 15 7	9 3 15 20 7	3	9	15 20 7
20 15 7	15 20 7	20	15	7

The full program#

build reads LeetCode's level-order notation, so you can paste the examples from any problem directly.

tree_patterns.go

package main
 
import (
	"fmt"
	"slices"
)
 
type Node struct {
	Val         int
	Left, Right *Node
}
 
const null = -1 << 31
 
// build makes a tree from LeetCode's level-order form, with null for a missing child.
func build(vals []int) *Node {
	if len(vals) == 0 || vals[0] == null {
		return nil
	}
	root := &Node{Val: vals[0]}
	queue := []*Node{root}
	for i := 1; i < len(vals); i += 2 {
		n := queue[0]
		queue = queue[1:]
		if vals[i] != null {
			n.Left = &Node{Val: vals[i]}
			queue = append(queue, n.Left)
		}
		if i+1 < len(vals) && vals[i+1] != null {
			n.Right = &Node{Val: vals[i+1]}
			queue = append(queue, n.Right)
		}
	}
	return root
}
 
// Bottom-up: return a value to the parent, keep a global best.
 
func diameter(root *Node) int {
	best := 0
	var height func(*Node) int
	height = func(n *Node) int {
		if n == nil {
			return 0
		}
		l, r := height(n.Left), height(n.Right)
		best = max(best, l+r)
		return 1 + max(l, r)
	}
	height(root)
	return best
}
 
// isBalanced returns -1 up the tree as soon as any subtree is unbalanced.
func isBalanced(root *Node) bool {
	var h func(*Node) int
	h = func(n *Node) int {
		if n == nil {
			return 0
		}
		l := h(n.Left)
		r := h(n.Right)
		if l < 0 || r < 0 || l-r > 1 || r-l > 1 {
			return -1
		}
		return 1 + max(l, r)
	}
	return h(root) >= 0
}
 
// lca of a general binary tree: a node returns whichever target it found below it.
func lca(n *Node, p, q int) *Node {
	if n == nil || n.Val == p || n.Val == q {
		return n
	}
	l, r := lca(n.Left, p, q), lca(n.Right, p, q)
	if l != nil && r != nil {
		return n // one target on each side
	}
	if l != nil {
		return l
	}
	return r
}
 
// Top-down: pass state to the children.
 
// goodNodes counts nodes with no larger value on the path from the root.
func goodNodes(root *Node) int {
	var dfs func(n *Node, maxSoFar int) int
	dfs = func(n *Node, maxSoFar int) int {
		if n == nil {
			return 0
		}
		good := 0
		if n.Val >= maxSoFar {
			good = 1
		}
		m := max(maxSoFar, n.Val)
		return good + dfs(n.Left, m) + dfs(n.Right, m)
	}
	return dfs(root, root.Val)
}
 
// pathSum lists every root-to-leaf path with the given sum: backtracking on a tree.
func pathSum(root *Node, target int) [][]int {
	var res [][]int
	var path []int
	var dfs func(n *Node, remain int)
	dfs = func(n *Node, remain int) {
		if n == nil {
			return
		}
		path = append(path, n.Val)
		remain -= n.Val
		if n.Left == nil && n.Right == nil && remain == 0 {
			res = append(res, slices.Clone(path))
		}
		dfs(n.Left, remain)
		dfs(n.Right, remain)
		path = path[:len(path)-1]
	}
	dfs(root, target)
	return res
}
 
// pathSumAny counts downward paths (any start, any end) with the given sum: prefix sums along the path.
func pathSumAny(root *Node, target int) int {
	seen := map[int]int{0: 1}
	var dfs func(n *Node, sum int) int
	dfs = func(n *Node, sum int) int {
		if n == nil {
			return 0
		}
		sum += n.Val
		count := seen[sum-target]
		seen[sum]++
		count += dfs(n.Left, sum) + dfs(n.Right, sum)
		seen[sum]-- // leave this path: the prefix no longer applies to other branches
		return count
	}
	return dfs(root, 0)
}
 
// Level by level.
 
// rightSideView keeps the last node of every level.
func rightSideView(root *Node) []int {
	var out []int
	level := []*Node{}
	if root != nil {
		level = append(level, root)
	}
	for len(level) > 0 {
		out = append(out, level[len(level)-1].Val)
		var next []*Node
		for _, n := range level {
			if n.Left != nil {
				next = append(next, n.Left)
			}
			if n.Right != nil {
				next = append(next, n.Right)
			}
		}
		level = next
	}
	return out
}
 
// zigzag reverses every other level.
func zigzag(root *Node) [][]int {
	var out [][]int
	level := []*Node{}
	if root != nil {
		level = append(level, root)
	}
	for len(level) > 0 {
		vals := make([]int, 0, len(level))
		var next []*Node
		for _, n := range level {
			vals = append(vals, n.Val)
			if n.Left != nil {
				next = append(next, n.Left)
			}
			if n.Right != nil {
				next = append(next, n.Right)
			}
		}
		if len(out)%2 == 1 {
			slices.Reverse(vals)
		}
		out = append(out, vals)
		level = next
	}
	return out
}
 
// BSTs: in-order is sorted.
 
// kthSmallest walks in-order with an explicit stack and stops after k nodes.
func kthSmallest(root *Node, k int) int {
	var stack []*Node
	n := root
	for {
		for n != nil {
			stack = append(stack, n)
			n = n.Left
		}
		n = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if k--; k == 0 {
			return n.Val
		}
		n = n.Right
	}
}
 
// Construction.
 
// buildTree from preorder (root first) and inorder (root splits left from right).
func buildTree(preorder, inorder []int) *Node {
	pos := make(map[int]int, len(inorder))
	for i, v := range inorder {
		pos[v] = i
	}
	next := 0
	var rec func(lo, hi int) *Node // the subtree whose values are inorder[lo:hi]
	rec = func(lo, hi int) *Node {
		if lo == hi {
			return nil
		}
		v := preorder[next]
		next++
		m := pos[v]
		return &Node{Val: v, Left: rec(lo, m), Right: rec(m+1, hi)}
	}
	return rec(0, len(inorder))
}
 
func preorderOf(n *Node) []int {
	if n == nil {
		return nil
	}
	return append(append([]int{n.Val}, preorderOf(n.Left)...), preorderOf(n.Right)...)
}
 
func main() {
	t := build([]int{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4})
	fmt.Println("diameter:", diameter(t), "balanced:", isBalanced(t), isBalanced(build([]int{1, 2, null, 3})))
	fmt.Println("lca(5,1):", lca(t, 5, 1).Val, "lca(5,4):", lca(t, 5, 4).Val)
	fmt.Println("good nodes:", goodNodes(build([]int{3, 1, 4, 3, null, 1, 5})))
	ps := build([]int{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1})
	fmt.Println("path sum 22:", pathSum(ps, 22))
	fmt.Println("downward paths of 8:", pathSumAny(build([]int{10, 5, -3, 3, 2, null, 11, 3, -2, null, 1}), 8))
	fmt.Println("right side:", rightSideView(t), "zigzag:", zigzag(t))
	fmt.Println("3rd smallest:", kthSmallest(build([]int{5, 3, 6, 2, 4, null, null, 1}), 3))
	fmt.Println("rebuilt:", preorderOf(buildTree([]int{3, 9, 20, 15, 7}, []int{9, 3, 15, 20, 7})))
}

Output

diameter: 5 balanced: true false
lca(5,1): 3 lca(5,4): 5
good nodes: 4
path sum 22: [[5 4 11 2] [5 8 4 5]]
downward paths of 8: 3
right side: [3 1 8 4] zigzag: [[3] [1 5] [6 2 0 8] [4 7]]
3rd smallest: 3
rebuilt: [3 9 20 15 7]

Complexity#

h is the height of the tree: log n when it is balanced, n when it degenerates into a line.

Problem	Time	Space
diameter, balanced, max path sum	O(n)	O(h) recursion
lowest common ancestor	O(n)	O(h)
good nodes, path sum II	O(n), plus copying paths for II	O(h)
path sum III with prefix sums	O(n)	O(h) map entries
right side view, zigzag	O(n)	O(width)
k-th smallest in BST	O(h + k)	O(h)
build from preorder + inorder	O(n)	O(n)

Recognizing the pattern#

Once you see a tree, ask the question from the flowchart: does the answer depend on subtrees (return values), ancestors (parameters), depth (BFS), or sorted order (in-order)? Then write the base case (n == nil) first and decide what a nil child contributes: height 0, sum 0, "not found."

Summary#

Choose the direction first: bottom-up returns values, top-down passes parameters.
In bottom-up problems, return what the parent needs (height) and keep the answer (diameter) outside.
LCA: return the target if you are on one; a node with results on both sides is the answer.
Path problems from the root are backtracking; paths from anywhere are prefix sums with undo.
Level order processes one slice per level, which gives row boundaries for free.
BST in-order is sorted; the iterative stack version can stop after k nodes.
Preorder gives roots and inorder splits subtrees; a map makes the rebuild O(n).