Pattern 7 of 18 · Core Structures

Trees

Recursion's best friend. DFS, BFS, and traversal order define most tree problems.

A tree is a hierarchical structure where each node has at most a fixed number of children (two, for binary trees). Almost every tree problem reduces to a traversal — decide what order you visit nodes in, and what you do at each one.

Key concepts

  • DFS traversals: preorder (node, left, right), inorder (left, node, right — gives sorted order for a BST), postorder (left, right, node).
  • BFS / level-order traversal: visit nodes level by level using a queue.
  • Recursion is the natural tool — a tree is defined in terms of smaller trees (its subtrees).

When to use it

  • The problem is naturally recursive: "the answer for this tree depends on the answer for its subtrees."
  • You need level-by-level information (BFS) versus depth-first structural information (DFS).

Tips

  • Decide what a function should return for a single node, then trust recursion to combine subtree results — don't track global state unless you have to.
  • Postorder is the natural order when a node's answer depends on both children's answers (e.g. height, diameter).
  • For a BST specifically, inorder traversal visits values in sorted order — a very useful property.

Practice problems (15)

Blind 75 (11):

More from Blind 150 (4):

← Linked ListTries →

See the full roadmap →