Know this before you start: “DFS: preorder / inorder / postorder”
Depth-first traversal: preorder, inorder, postorder
Visit a node, its left subtree and its right subtree; the three orders only differ in when you handle the node itself.
The idea
A binary tree node has a value and up to two children. Depth-first search goes as deep as possible down one side before coming back, which recursion does naturally.
Preorder handles the node first (copying a tree), inorder in the middle (gives a BST's values sorted), postorder last (you need the children's answers first, like computing a height).
Most tree problems are one of these, with “handle the node” replaced by the problem's work.
See it step by step
Tree 2 with children 1 and 3
- Preorder (node, left, right): 2, 1, 3
- Inorder (left, node, right): 1, 2, 3, sorted, because it's a BST
- Postorder (left, right, node): 1, 3, 2
In code (Python)
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def preorder(node, out):
if node:
out.append(node.val)
preorder(node.left, out)
preorder(node.right, out)
return out
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
return out
def postorder(node, out):
if node:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.val)
return out
root = TreeNode(2, TreeNode(1), TreeNode(3))
print(preorder(root, []), inorder(root, []), postorder(root, []))
# [2, 1, 3] [1, 2, 3] [1, 3, 2]O(n) time, O(h) space for a tree of height h.
When you'll use it
- Almost every tree problem: sums, paths, depth, checking a BST, building or copying trees.
Common mistakes
- Forgetting the empty-tree base case.
- Using the wrong order: needing children's results means postorder.
