LeetCode Solutions← Back to Patterns
Trees & GraphsEasy
Tree Traversal
Visit every node in a defined order (pre/in/post/level).
How it works
Tree Traversal defines the order in which nodes are visited. There are four main types: (1) Preorder (root → left → right): useful for copying or serializing a tree. (2) Inorder (left → root → right): produces sorted output for BSTs. (3) Postorder (left → right → root): useful for deletion and bottom-up computation. (4) Level-order (BFS): visits nodes level by level, good for finding depth or printing by level. Each traversal can be implemented recursively or iteratively. Iterative inorder uses a stack with a current-node pointer; iterative level-order uses a queue. Morris Traversal achieves O(1) space inorder using threaded binary trees.
Interactive Playground
In-order: Left → Root → Right. Start at root, go left first.
Speed
When to use
- Serialize or deserialize a tree
- Validate BST properties
- Path sum and ancestor problems
✅Tips
1For BST validation, pass min/max bounds down the recursion — a node is valid only if its value is within the allowed range.
2For path sum problems, subtract the node value from the target as you go down, check if target == 0 at leaves.
3Iterative inorder: push nodes left while possible, then pop, visit, and move right.
4Serialize with preorder + null markers; deserialize by consuming the sequence with a pointer/iterator.
❌Common Mistakes
!Using node.val > root.val for BST validation — this only checks the parent, not all ancestors.
!Confusing preorder (root first) and postorder (root last) when the problem needs bottom-up info.
!Not handling null nodes when serializing — the null markers are needed to reconstruct the exact shape.
!For path sum, checking at every node instead of only at leaves — may produce false positives.
💡 Key Insight:Inorder traversal of a BST yields a sorted array — a key BST property.