This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬
Binary Tree Traversal
Knowledge Summary
Definition of a Binary Tree
A tree in which each node has at most two children, namely the left child and the right child.
Three Traversal Orders
| Traversal Order | Visiting Order | Mnemonic |
|---|---|---|
| Preorder | Root -> Left -> Right | Root Left Right |
| Inorder | Left -> Root -> Right | Left Root Right |
| Postorder | Left -> Right -> Root | Left Right Root |
Traversal Example
A
/ \
B C
/ \ \
D E F- Preorder: A B D E C F
- Inorder: D B E A C F
- Postorder: D E B F C A
- Level order: A B C D E F
Reconstructing a Binary Tree from Traversal Sequences
- Preorder + inorder -> can uniquely determine a binary tree
- Postorder + inorder -> can uniquely determine a binary tree
- Preorder + postorder -> cannot uniquely determine a binary tree unless it is a full binary tree
How reconstruction works:
- The first element of preorder, or the last element of postorder, is the root
- Find the root in the inorder sequence; the left part is the left subtree and the right part is the right subtree
- Recursively process the left and right subtrees
Level-Order Traversal
Implemented using a queue, visiting all nodes level by level from left to right.