Pre → Root → Left → Right IN → Left → Root → Right Post → Left → Right → Root
Pre-Order: First node of pre-order traversal output is always the root. Post-Order: Last node of post-order traversal output is always the root.
- In-order traversal gives us the relative ordering of nodes (left, root, right).
- Pre-order or Post-order tells us which node appears first or last, helping us determine the root and recursive subtrees.
Why Can’t “Pre-order + Post-order” Reconstruct a Tree?
With Pre-order and Post-order, we know:
- Pre-order tells us the root first.
- Post-order tells us the root last.
However, we don’t know where to split the tree into left and right subtrees without in-order information.
Problems: