Tree Traversals (Inorder, Preorder, Postorder, Level Order)
Table of Contents
All binary tree traversal methods with recursive and iterative implementations, Morris traversal, and tree construction from traversals.
Binary Tree Node
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
The Example Tree
We will use this tree throughout the entire document:
Structure:
- Root: 1
- 1's left child: 2, right child: 3
- 2's left child: 4, right child: 5
- 3's right child: 6
- 5's left child: 7
- Nodes 4, 7, 6 are leaf nodes
Statistics:
- 7 nodes total
- Height: 3 (longest path from root to leaf: 1 -> 2 -> 5 -> 7)
- It is NOT a BST (just a general binary tree)
The Three DFS Traversals
1. Inorder Traversal (Left -> Root -> Right)
Intuition
Visit the left subtree first, then the current node, then the right subtree. If you imagine projecting the tree downward onto a horizontal line, inorder traversal visits nodes from left to right.
Step-by-Step Trace
1
/ \
2 3
/ \ \
4 5 6
/
7
Call: inorder(1)
Call: inorder(2) -- go left from 1
Call: inorder(4) -- go left from 2
Call: inorder(null) -- 4 has no left child, return
VISIT 4 -- process node 4
Call: inorder(null) -- 4 has no right child, return
VISIT 2 -- process node 2
Call: inorder(5) -- go right from 2
Call: inorder(7) -- go left from 5
Call: inorder(null) -- 7 has no left child, return
VISIT 7 -- process node 7
Call: inorder(null) -- 7 has no right child, return
VISIT 5 -- process node 5
Call: inorder(null) -- 5 has no right child, return
VISIT 1 -- process node 1
Call: inorder(3) -- go right from 1
Call: inorder(null) -- 3 has no left child, return
VISIT 3 -- process node 3
Call: inorder(6) -- go right from 3
Call: inorder(null) -- 6 has no left child, return
VISIT 6 -- process node 6
Call: inorder(null) -- 6 has no right child, return
Result: [4, 2, 7, 5, 1, 3, 6]
Visual: Which nodes appear when
Inorder: [4, 2, 7, 5, 1, 3, 6]
Key Property
Inorder traversal of a Binary Search Tree (BST) produces elements in sorted (ascending) order. This is because in a BST, left < root < right, so visiting left first, then root, then right gives a sorted sequence.
Inorder: [2, 3, 4, 5, 6, 7, 8] -- sorted!
This property is the foundation for many BST algorithms:
- Validate BST (check if inorder is sorted)
- Find kth smallest element
- Convert BST to sorted array
Recursive Implementation
void inorder(TreeNode* root, vector<int>& result) {
if (!root) return;
inorder(root->left, result); // L
result.push_back(root->val); // Root
inorder(root->right, result); // R
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorder(root, result);
return result;
}
Iterative Implementation (Using Stack)
The key insight: we need to go as far left as possible, then process, then go right. The stack stores nodes we have visited but not yet processed.
Algorithm:
1. Push all left children onto stack (go as far left as possible)
2. Pop a node, process it
3. Move to its right child
4. Repeat
Stack trace for our example tree:
curr = 1: push 1, go left
curr = 2: push 2, go left
curr = 4: push 4, go left
curr = null: stop pushing
Pop 4, process 4. Output: [4]
curr = 4->right = null
Pop 2, process 2. Output: [4, 2]
curr = 2->right = 5
curr = 5: push 5, go left
curr = 7: push 7, go left
curr = null: stop pushing
Pop 7, process 7. Output: [4, 2, 7]
curr = 7->right = null
Pop 5, process 5. Output: [4, 2, 7, 5]
curr = 5->right = null
Pop 1, process 1. Output: [4, 2, 7, 5, 1]
curr = 1->right = 3
curr = 3: push 3, go left
curr = null: stop pushing
Pop 3, process 3. Output: [4, 2, 7, 5, 1, 3]
curr = 3->right = 6
curr = 6: push 6, go left
curr = null: stop pushing
Pop 6, process 6. Output: [4, 2, 7, 5, 1, 3, 6]
curr = 6->right = null
Stack empty, curr = null. Done!
vector<int> inorderIterative(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr || !st.empty()) {
// Go as far left as possible
while (curr) {
st.push(curr);
curr = curr->left;
}
// Process the leftmost unprocessed node
curr = st.top();
st.pop();
result.push_back(curr->val);
// Move to right subtree
curr = curr->right;
}
return result;
}
Time: O(n) --- each node is pushed and popped exactly once. Space: O(h) where h is the height (O(n) worst case for skewed tree, O(log n) for balanced).
2. Preorder Traversal (Root -> Left -> Right)
Intuition
Visit the current node first, then the left subtree, then the right subtree. This is the most natural "top-down" traversal --- you process a node as soon as you arrive at it, before exploring its children.
Think of it as: you're entering a building and writing down each room number as you enter it, before exploring its sub-rooms.
Step-by-Step Trace
1
/ \
2 3
/ \ \
4 5 6
/
7
VISIT 1
VISIT 2 -- left of 1
VISIT 4 -- left of 2
(null left, null right)
VISIT 5 -- right of 2
VISIT 7 -- left of 5
(null left, null right)
(null right)
VISIT 3 -- right of 1
(null left)
VISIT 6 -- right of 3
(null left, null right)
Result: [1, 2, 4, 5, 7, 3, 6]
Visual
Preorder: [1, 2, 4, 5, 7, 3, 6]
Key Properties
- The first element is always the root of the tree/subtree.
- Preorder is used to serialize (save) a tree --- you can reconstruct the tree from preorder + one additional traversal.
- Preorder corresponds to the order you would visit nodes doing a DFS with "process on entry".
Recursive Implementation
void preorder(TreeNode* root, vector<int>& result) {
if (!root) return;
result.push_back(root->val); // Root
preorder(root->left, result); // L
preorder(root->right, result); // R
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
preorder(root, result);
return result;
}
Iterative Implementation
Simpler than inorder! Push root, then repeatedly pop and push right child first (so left is processed first due to LIFO).
Stack trace:
Push 1.
Stack: [1]
Pop 1, process 1. Output: [1]
Push right(3), then left(2).
Stack: [3, 2]
Pop 2, process 2. Output: [1, 2]
Push right(5), then left(4).
Stack: [3, 5, 4]
Pop 4, process 4. Output: [1, 2, 4]
No children.
Stack: [3, 5]
Pop 5, process 5. Output: [1, 2, 4, 5]
Push right(null), push left(7).
Stack: [3, 7]
Pop 7, process 7. Output: [1, 2, 4, 5, 7]
No children.
Stack: [3]
Pop 3, process 3. Output: [1, 2, 4, 5, 7, 3]
Push right(6), no left.
Stack: [6]
Pop 6, process 6. Output: [1, 2, 4, 5, 7, 3, 6]
No children.
Stack: []
Done!
vector<int> preorderIterative(TreeNode* root) {
if (!root) return {};
vector<int> result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
// Push RIGHT first, so LEFT is processed first (LIFO)
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return result;
}
3. Postorder Traversal (Left -> Right -> Root)
Intuition
Visit the left subtree, then the right subtree, then the current node last. This is a "bottom-up" traversal --- you process children before their parent.
Think of it as: you can only report on a room after you have fully explored all its sub-rooms.
Step-by-Step Trace
1
/ \
2 3
/ \ \
4 5 6
/
7
postorder(4): null, null -> VISIT 4
postorder(7): null, null -> VISIT 7
postorder(5): visited 7, null -> VISIT 5
postorder(2): visited 4, visited 5 -> VISIT 2
postorder(6): null, null -> VISIT 6
postorder(3): null, visited 6 -> VISIT 3
postorder(1): visited 2, visited 3 -> VISIT 1
Result: [4, 7, 5, 2, 6, 3, 1]
Visual
Postorder: [4, 7, 5, 2, 6, 3, 1]
Key Properties
- The last element is always the root of the tree.
- Used for deleting/freeing a tree (delete children before parent).
- Used for evaluating expression trees (evaluate operands before operator).
- Used for calculating subtree properties (e.g., subtree size, height) in bottom-up fashion.
- Postorder corresponds to DFS with "process on exit".
Recursive Implementation
void postorder(TreeNode* root, vector<int>& result) {
if (!root) return;
postorder(root->left, result); // L
postorder(root->right, result); // R
result.push_back(root->val); // Root
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
postorder(root, result);
return result;
}
Iterative Implementation
Postorder is the trickiest to do iteratively. There are several approaches:
Method 1: Modified Preorder + Reverse
Observation: Postorder is L, R, Root. If we do a "modified preorder" of Root, R, L (swap left and right), then reverse, we get L, R, Root = postorder!
Modified preorder (Root, R, L): [1, 3, 6, 2, 5, 7, 4]
Reversed: [4, 7, 5, 2, 6, 3, 1] = postorder!
vector<int> postorderIterative(TreeNode* root) {
if (!root) return {};
vector<int> result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
// Push LEFT first (opposite of preorder), so RIGHT is processed first
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
}
reverse(result.begin(), result.end());
return result;
}
Method 2: Single Stack with Last Visited Tracking
This approach does not require reversing and processes nodes in true postorder.
vector<int> postorderIterativeSingleStack(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* curr = root;
TreeNode* lastVisited = nullptr;
while (curr || !st.empty()) {
// Go as far left as possible
while (curr) {
st.push(curr);
curr = curr->left;
}
TreeNode* top = st.top();
// If right child exists and hasn't been visited, go right
if (top->right && top->right != lastVisited) {
curr = top->right;
} else {
// Process this node
result.push_back(top->val);
lastVisited = top;
st.pop();
}
}
return result;
}
How Method 2 works, step by step:
Tree:
1
/ \
2 3
/ \ \
4 5 6
/
7
Step | Stack | Action | Output
------|------------------|----------------------------|--------
1 | [1] | Push 1, go left |
2 | [1, 2] | Push 2, go left |
3 | [1, 2, 4] | Push 4, go left (null) |
4 | [1, 2, 4] | top=4, no right, VISIT 4 | [4]
5 | [1, 2] | top=2, right=5 exists |
6 | [1, 2, 5] | Push 5, go left |
7 | [1, 2, 5, 7] | Push 7, go left (null) |
8 | [1, 2, 5, 7] | top=7, no right, VISIT 7 | [4,7]
9 | [1, 2, 5] | top=5, right=null, VISIT 5 | [4,7,5]
10 | [1, 2] | top=2, right=5 (visited!) |
| | VISIT 2 | [4,7,5,2]
11 | [1] | top=1, right=3 exists |
12 | [1, 3] | Push 3, go left (null) |
13 | [1, 3] | top=3, right=6 exists |
14 | [1, 3, 6] | Push 6, go left (null) |
15 | [1, 3, 6] | top=6, no right, VISIT 6 | [4,7,5,2,6]
16 | [1, 3] | top=3, right=6 (visited!) |
| | VISIT 3 | [4,7,5,2,6,3]
17 | [1] | top=1, right=3 (visited!) |
| | VISIT 1 | [4,7,5,2,6,3,1]
Done! Output: [4, 7, 5, 2, 6, 3, 1]
4. Level Order Traversal (BFS)
Intuition
Visit nodes level by level, from top to bottom, left to right within each level. Uses a queue (BFS), not a stack.
Visual
Result: [[1], [2, 3], [4, 5, 6], [7]] | Flat: [1, 2, 3, 4, 5, 6, 7]
Queue Trace
Queue state after each level:
Initial: queue = [1]
Level 0: Process 1
Enqueue children: 2, 3
Queue: [2, 3]
Level result: [1]
Level 1: Process 2, then 3
From 2: enqueue 4, 5
From 3: enqueue 6
Queue: [4, 5, 6]
Level result: [2, 3]
Level 2: Process 4, 5, 6
From 4: no children
From 5: enqueue 7
From 6: no children
Queue: [7]
Level result: [4, 5, 6]
Level 3: Process 7
From 7: no children
Queue: []
Level result: [7]
Final: [[1], [2, 3], [4, 5, 6], [7]]
Implementation
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size(); // Number of nodes at current level
vector<int> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
return result;
}
The size = q.size() trick: Before processing a level, we capture the current
queue size. This tells us exactly how many nodes belong to the current level. All nodes
enqueued during this loop belong to the next level.
Recursive Level Order (DFS approach)
You can also implement level order using DFS by passing the level number:
void dfsLevel(TreeNode* root, int level, vector<vector<int>>& result) {
if (!root) return;
if (level >= (int)result.size()) {
result.push_back({}); // New level
}
result[level].push_back(root->val);
dfsLevel(root->left, level + 1, result);
dfsLevel(root->right, level + 1, result);
}
vector<vector<int>> levelOrderDFS(TreeNode* root) {
vector<vector<int>> result;
dfsLevel(root, 0, result);
return result;
}
Time and Space
| Approach | Time | Space |
|---|---|---|
| BFS (queue) | O(n) | O(w) where w = max width of tree |
| DFS (recursive) | O(n) | O(h) where h = height |
For a complete binary tree: w = n/2, h = log n. BFS uses more space. For a skewed tree: w = 1, h = n. DFS uses more space.
Morris Traversal --- O(1) Space!
The Problem with Standard Approaches
Both recursive and iterative traversals use O(h) space (recursion stack or explicit stack). Can we traverse with O(1) extra space?
The Key Idea: Threaded Binary Tree
Morris traversal temporarily modifies the tree by creating threads --- right pointers from a node's inorder predecessor back to the node itself. These threads act as "breadcrumbs" that allow us to return to a node without a stack.
How Threads Work
The inorder predecessor of node X is the rightmost node in X's left subtree. Its right pointer is normally null (since it's the rightmost). Morris traversal temporarily sets this right pointer to X, creating a thread.
Morris Inorder: Step-by-Step
Tree:
1
/ \
2 3
/ \ \
4 5 6
/
7
Algorithm:
curr = root
For each node:
If no left child:
VISIT curr
curr = curr->right
If has left child:
Find inorder predecessor (rightmost in left subtree)
If predecessor's right is null:
Create thread: predecessor->right = curr
curr = curr->left
If predecessor's right points to curr (thread exists):
Remove thread: predecessor->right = null
VISIT curr
curr = curr->right
Detailed trace:
Step 1: curr = 1
Has left child (2).
Find predecessor: go left to 2, then right to 5.
5->right is null -> CREATE THREAD: 5->right = 1
curr = 2
1 <---------+
/ \ |
2 3 thread
/ \ \ |
4 5----+ 6
/
7
Step 2: curr = 2
Has left child (4).
Find predecessor: go left to 4. 4->right is null.
CREATE THREAD: 4->right = 2
curr = 4
1 <---------+
/ \ |
2 3 thread
/ \ \ |
4---+ 5----+ 6
| thread |
+-->2 /
7
Step 3: curr = 4
No left child.
VISIT 4. Output: [4]
curr = 4->right = 2 (follow thread!)
Step 4: curr = 2
Has left child (4).
Find predecessor: go left to 4. 4->right = 2 (thread exists!)
REMOVE THREAD: 4->right = null
VISIT 2. Output: [4, 2]
curr = 2->right = 5
Step 5: curr = 5
Has left child (7).
Find predecessor: go left to 7. 7->right is null.
CREATE THREAD: 7->right = 5
curr = 7
Step 6: curr = 7
No left child.
VISIT 7. Output: [4, 2, 7]
curr = 7->right = 5 (follow thread!)
Step 7: curr = 5
Has left child (7).
Find predecessor: go left to 7. 7->right = 5 (thread exists!)
REMOVE THREAD: 7->right = null
VISIT 5. Output: [4, 2, 7, 5]
curr = 5->right = 1 (follow thread!)
Step 8: curr = 1
Has left child (2).
Find predecessor: 2 -> 5. 5->right = 1 (thread exists!)
REMOVE THREAD: 5->right = null
VISIT 1. Output: [4, 2, 7, 5, 1]
curr = 1->right = 3
Step 9: curr = 3
No left child.
VISIT 3. Output: [4, 2, 7, 5, 1, 3]
curr = 3->right = 6
Step 10: curr = 6
No left child.
VISIT 6. Output: [4, 2, 7, 5, 1, 3, 6]
curr = 6->right = null
curr is null. Done!
Final: [4, 2, 7, 5, 1, 3, 6] (correct inorder!)
Morris Inorder C++ Code
vector<int> morrisInorder(TreeNode* root) {
vector<int> result;
TreeNode* curr = root;
while (curr) {
if (!curr->left) {
// No left child: visit and go right
result.push_back(curr->val);
curr = curr->right;
} else {
// Find inorder predecessor
TreeNode* pred = curr->left;
while (pred->right && pred->right != curr) {
pred = pred->right;
}
if (!pred->right) {
// First visit: create thread
pred->right = curr;
curr = curr->left;
} else {
// Second visit: remove thread, process node
pred->right = nullptr;
result.push_back(curr->val);
curr = curr->right;
}
}
}
return result;
}
Morris Preorder C++ Code
Almost identical to Morris inorder, but we visit the node when creating the thread (first visit) instead of when removing it (second visit).
vector<int> morrisPreorder(TreeNode* root) {
vector<int> result;
TreeNode* curr = root;
while (curr) {
if (!curr->left) {
result.push_back(curr->val);
curr = curr->right;
} else {
TreeNode* pred = curr->left;
while (pred->right && pred->right != curr) {
pred = pred->right;
}
if (!pred->right) {
result.push_back(curr->val); // Visit HERE (before going left)
pred->right = curr;
curr = curr->left;
} else {
pred->right = nullptr;
// Don't visit here (already visited on first encounter)
curr = curr->right;
}
}
}
return result;
}
Morris Traversal Complexity
| Aspect | Value | Explanation |
|---|---|---|
| Time | O(n) | Each edge traversed at most 3 times (twice for finding predecessor, once for following thread) |
| Space | O(1) | No stack, no recursion, only a few pointers |
| Modifies tree? | Temporarily yes, but restored to original |
When to use Morris traversal: When O(1) space is required and you are allowed to temporarily modify the tree (e.g., you own the tree in memory).
Summary Table
Relationships Between Traversals
For a BST, the following identity holds:
- Inorder gives SORTED order
- Preorder gives the ORDER OF INSERTION (if tree was built by insertion)
For any binary tree:
- Preorder + Inorder -> uniquely determines the tree
- Postorder + Inorder -> uniquely determines the tree
- Preorder + Postorder -> NOT unique (ambiguous for non-full trees)
Constructing Trees from Traversals
Construct from Preorder + Inorder (LC 105)
The Algorithm
- The first element of preorder is always the root.
- Find this root in inorder. Everything to its left is the left subtree, everything to its right is the right subtree.
- Use the sizes to split the preorder array correspondingly.
- Recurse.
Visual Walkthrough
Preorder: [3, 9, 20, 15, 7]
Inorder: [9, 3, 15, 20, 7]
Step 1: Root = 3 (first in preorder)
In inorder, 3 is at index 1.
Left inorder: [9] (1 element)
Right inorder: [15, 20, 7] (3 elements)
Left preorder: [9] (next 1 element after root)
Right preorder: [20, 15, 7] (remaining 3 elements)
3
/ \
? ?
[9] [20, 15, 7] / [15, 20, 7]
Step 2: Left subtree
Preorder: [9], Inorder: [9]
Root = 9, no children.
3
/ \
9 ?
Step 3: Right subtree
Preorder: [20, 15, 7], Inorder: [15, 20, 7]
Root = 20 (first in preorder)
In inorder, 20 is at index 1.
Left inorder: [15] Right inorder: [7]
Left preorder: [15] Right preorder: [7]
3
/ \
9 20
/ \
15 7
C++ Code
class Solution {
unordered_map<int, int> inorderIndex;
int preIdx;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
preIdx = 0;
for (int i = 0; i < (int)inorder.size(); i++) {
inorderIndex[inorder[i]] = i;
}
return build(preorder, 0, (int)inorder.size() - 1);
}
private:
TreeNode* build(vector<int>& preorder, int inLeft, int inRight) {
if (inLeft > inRight) return nullptr;
int rootVal = preorder[preIdx++];
TreeNode* root = new TreeNode(rootVal);
int inIdx = inorderIndex[rootVal];
root->left = build(preorder, inLeft, inIdx - 1);
root->right = build(preorder, inIdx + 1, inRight);
return root;
}
};
Time: O(n) with hash map for O(1) lookup in inorder. Space: O(n) for hash map + O(h) recursion stack.
Construct from Postorder + Inorder (LC 106)
Same idea, but the last element of postorder is the root. We build right subtree first (since postorder processes right before root in reverse).
Postorder: [9, 15, 7, 20, 3]
Inorder: [9, 3, 15, 20, 7]
Root = 3 (last in postorder)
In inorder: left = [9], right = [15, 20, 7]
Build RIGHT first, then LEFT (reverse postorder).
class Solution {
unordered_map<int, int> inorderIndex;
int postIdx;
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
postIdx = (int)postorder.size() - 1;
for (int i = 0; i < (int)inorder.size(); i++) {
inorderIndex[inorder[i]] = i;
}
return build(postorder, 0, (int)inorder.size() - 1);
}
private:
TreeNode* build(vector<int>& postorder, int inLeft, int inRight) {
if (inLeft > inRight) return nullptr;
int rootVal = postorder[postIdx--];
TreeNode* root = new TreeNode(rootVal);
int inIdx = inorderIndex[rootVal];
// Build RIGHT subtree first! (reverse of preorder approach)
root->right = build(postorder, inIdx + 1, inRight);
root->left = build(postorder, inLeft, inIdx - 1);
return root;
}
};
Why Preorder + Postorder is NOT Unique
Preorder: [1, 2] | Postorder: [2, 1]
Both have preorder [1,2] and postorder [2,1]. We cannot determine if 2 is a left or right child without inorder information.
Exception: If the tree is a FULL binary tree (every node has 0 or 2 children), then preorder + postorder uniquely determines the tree.
Classic Problems with Full Solutions
1. Binary Tree Inorder Traversal (LC 94)
Both recursive and iterative solutions covered above. Here is the clean final version:
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr || !st.empty()) {
while (curr) {
st.push(curr);
curr = curr->left;
}
curr = st.top(); st.pop();
result.push_back(curr->val);
curr = curr->right;
}
return result;
}
};
2. Binary Tree Level Order Traversal (LC 102)
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
return result;
}
};
3. Zigzag Level Order Traversal (LC 103)
Level order, but alternate direction each level (left-to-right, then right-to-left).
Result: [[3], [20, 9], [15, 7]]
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> result;
queue<TreeNode*> q;
q.push(root);
bool leftToRight = true;
while (!q.empty()) {
int size = q.size();
vector<int> level(size);
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
// Determine position based on direction
int idx = leftToRight ? i : (size - 1 - i);
level[idx] = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
leftToRight = !leftToRight;
}
return result;
}
};
4. Binary Tree Right Side View (LC 199)
Return the values visible when looking at the tree from the right side.
Right side view: [1, 3, 4] (at each level, the rightmost node)
Approach 1: BFS (last node of each level)
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (!root) return {};
vector<int> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
if (i == size - 1) {
result.push_back(node->val); // Last node in level
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return result;
}
};
Approach 2: DFS (visit right before left, track depth)
class Solution {
public:
vector<int> result;
vector<int> rightSideView(TreeNode* root) {
dfs(root, 0);
return result;
}
void dfs(TreeNode* node, int depth) {
if (!node) return;
if (depth == (int)result.size()) {
result.push_back(node->val); // First node at this depth from right
}
dfs(node->right, depth + 1); // Visit right FIRST
dfs(node->left, depth + 1);
}
};
5. Construct Binary Tree from Preorder and Inorder (LC 105)
Already covered in detail above. See "Construct from Preorder + Inorder" section.
6. Serialize and Deserialize Binary Tree (LC 297)
Convert a tree to a string and back. Use preorder traversal with null markers.
Serialized (preorder): "1,2,#,#,3,4,#,#,5,#,#" (# represents null)
class Codec {
public:
// Serialize: Preorder traversal with null markers
string serialize(TreeNode* root) {
if (!root) return "#";
return to_string(root->val) + ","
+ serialize(root->left) + ","
+ serialize(root->right);
}
// Deserialize: Rebuild from preorder
TreeNode* deserialize(string data) {
queue<string> tokens;
string token;
istringstream stream(data);
while (getline(stream, token, ',')) {
tokens.push(token);
}
return build(tokens);
}
private:
TreeNode* build(queue<string>& tokens) {
if (tokens.empty()) return nullptr;
string val = tokens.front();
tokens.pop();
if (val == "#") return nullptr;
TreeNode* node = new TreeNode(stoi(val));
node->left = build(tokens);
node->right = build(tokens);
return node;
}
};
Alternative: Level-order serialization
class Codec {
public:
string serialize(TreeNode* root) {
if (!root) return "";
string result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (node) {
result += to_string(node->val) + ",";
q.push(node->left);
q.push(node->right);
} else {
result += "#,";
}
}
return result;
}
TreeNode* deserialize(string data) {
if (data.empty()) return nullptr;
vector<string> tokens;
string token;
istringstream stream(data);
while (getline(stream, token, ',')) {
if (!token.empty()) tokens.push_back(token);
}
if (tokens.empty() || tokens[0] == "#") return nullptr;
TreeNode* root = new TreeNode(stoi(tokens[0]));
queue<TreeNode*> q;
q.push(root);
int i = 1;
while (!q.empty() && i < (int)tokens.size()) {
TreeNode* node = q.front(); q.pop();
if (i < (int)tokens.size() && tokens[i] != "#") {
node->left = new TreeNode(stoi(tokens[i]));
q.push(node->left);
}
i++;
if (i < (int)tokens.size() && tokens[i] != "#") {
node->right = new TreeNode(stoi(tokens[i]));
q.push(node->right);
}
i++;
}
return root;
}
};
7. Vertical Order Traversal (LC 987)
Assign each node a column (root = 0, left child = col-1, right child = col+1) and a row (root = 0, children = row+1). Report nodes grouped by column, then row, then value.
Result: [[9], [3, 15], [20], [7]]
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
// {col -> {row -> sorted values}}
map<int, map<int, multiset<int>>> nodes;
// BFS with (node, row, col)
queue<tuple<TreeNode*, int, int>> q;
q.push({root, 0, 0});
while (!q.empty()) {
auto [node, row, col] = q.front(); q.pop();
nodes[col][row].insert(node->val);
if (node->left) q.push({node->left, row + 1, col - 1});
if (node->right) q.push({node->right, row + 1, col + 1});
}
vector<vector<int>> result;
for (auto& [col, rows] : nodes) {
vector<int> colVals;
for (auto& [row, vals] : rows) {
for (int val : vals) {
colVals.push_back(val);
}
}
result.push_back(colVals);
}
return result;
}
};
8. Boundary of Binary Tree (LC 545)
Return the boundary of the tree in anti-clockwise order: left boundary + leaves + right boundary (reversed).
- Left boundary: [1, 2, 4] (go left, exclude leaves)
- Leaves: [4, 8, 9, 6, 7] (all leaves, left to right)
- Right boundary: [7, 3, 1] (go right, exclude leaves, reversed)
- Left boundary excludes leaves; leaves listed separately; right boundary excludes leaves. Root listed once at start.
- Boundary: [1, 2, 4, 8, 9, 6, 7, 3]
class Solution {
public:
vector<int> boundaryOfBinaryTree(TreeNode* root) {
if (!root) return {};
vector<int> result;
if (!isLeaf(root)) {
result.push_back(root->val);
}
// Left boundary (excluding root and leaves)
addLeftBoundary(root->left, result);
// All leaves (left to right)
addLeaves(root, result);
// Right boundary (excluding root and leaves, in reverse)
addRightBoundary(root->right, result);
return result;
}
private:
bool isLeaf(TreeNode* node) {
return node && !node->left && !node->right;
}
void addLeftBoundary(TreeNode* node, vector<int>& result) {
while (node) {
if (!isLeaf(node)) {
result.push_back(node->val);
}
node = node->left ? node->left : node->right;
}
}
void addLeaves(TreeNode* node, vector<int>& result) {
if (!node) return;
if (isLeaf(node)) {
result.push_back(node->val);
return;
}
addLeaves(node->left, result);
addLeaves(node->right, result);
}
void addRightBoundary(TreeNode* node, vector<int>& result) {
vector<int> temp;
while (node) {
if (!isLeaf(node)) {
temp.push_back(node->val);
}
node = node->right ? node->right : node->left;
}
// Add in reverse order
for (int i = (int)temp.size() - 1; i >= 0; i--) {
result.push_back(temp[i]);
}
}
};
Additional Important Traversal Variants
Reverse Level Order
Process levels from bottom to top.
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result = levelOrder(root); // Normal level order
reverse(result.begin(), result.end());
return result;
}
Left Side View
Same as right side view, but take first node of each level:
vector<int> leftSideView(TreeNode* root) {
if (!root) return {};
vector<int> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
if (i == 0) result.push_back(node->val); // First node in level
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return result;
}
Maximum Width of Binary Tree (LC 662)
Width of a level = position of rightmost node - position of leftmost node + 1. Use indexing: root = 1, left child = 2i, right child = 2i+1.
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int maxWidth = 0;
queue<pair<TreeNode*, unsigned long long>> q;
q.push({root, 0});
while (!q.empty()) {
int size = q.size();
unsigned long long minIdx = q.front().second;
unsigned long long first, last;
for (int i = 0; i < size; i++) {
auto [node, idx] = q.front(); q.pop();
idx -= minIdx; // Normalize to prevent overflow
if (i == 0) first = idx;
if (i == size - 1) last = idx;
if (node->left) q.push({node->left, 2 * idx});
if (node->right) q.push({node->right, 2 * idx + 1});
}
maxWidth = max(maxWidth, (int)(last - first + 1));
}
return maxWidth;
}
};
Tree Diameter (using DFS Postorder)
The diameter of a tree is the longest path between any two nodes. It passes through the deepest points of some subtree.
Diameter = 3 (path: 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3)
class Solution {
int diameter;
public:
int diameterOfBinaryTree(TreeNode* root) {
diameter = 0;
height(root);
return diameter;
}
int height(TreeNode* node) {
if (!node) return 0;
int leftH = height(node->left); // Postorder: compute children first
int rightH = height(node->right);
diameter = max(diameter, leftH + rightH); // Update diameter through this node
return 1 + max(leftH, rightH);
}
};
Complexity Summary for All Traversals
Final Decision Guide: Which Traversal to Use
Need sorted order from BST?
-> Inorder
Need to serialize / reconstruct tree?
-> Preorder (or level order)
Need to process children before parent (bottom-up)?
-> Postorder
Need level-by-level information?
-> Level order (BFS)
Need O(1) space traversal?
-> Morris traversal
Need to evaluate expression tree?
-> Postorder (evaluate operands before operator)
Need to create a copy of the tree?
-> Preorder (create node, then recurse on children)
Need to delete/free tree memory?
-> Postorder (delete children before parent)
Need right/left side view?
-> Level order or DFS with depth tracking
Need zigzag traversal?
-> Level order with direction flag
Need vertical order?
-> BFS/DFS with column tracking + ordered map
Traversals in a Binary Search Tree (BST)
Everything above applies to any binary tree. A BST adds one constraint:
For every node:
all values in left subtree < node.val
all values in right subtree > node.val
This single property dramatically changes what each traversal means and unlocks operations that are impossible (or expensive) on a general binary tree.
The BST We Will Use
20
/ \
10 30
/ \ \
5 15 35
/ \ \
3 7 17
- Valid BST: every node satisfies left < root < right.
- Height: 3, Nodes: 9
Inorder Traversal Gives Sorted Order
This is the single most important BST fact.
Because we visit left, then root, then right — and left < root < right — inorder traversal on a BST always produces values in ascending sorted order.
Inorder on our BST:
inorder(20)
inorder(10)
inorder(5)
inorder(3) -> VISIT 3
VISIT 5
inorder(7) -> VISIT 7
VISIT 10
inorder(15)
(no left)
VISIT 15
inorder(17) -> VISIT 17
VISIT 20
inorder(30)
(no left)
VISIT 30
inorder(35) -> VISIT 35
Result: [3, 5, 7, 10, 15, 17, 20, 30, 35] ← sorted!
Why this matters:
- Kth smallest element — just do inorder, stop at the kth visit.
- Validate BST — inorder and check that each value > previous.
- Convert BST to sorted linked list — inorder with pointer rewiring.
- Find closest value — inorder gives you a sorted array to binary search.
Kth Smallest Element in a BST (LC 230)
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int count = 0, result = 0;
inorder(root, k, count, result);
return result;
}
private:
void inorder(TreeNode* node, int k, int& count, int& result) {
if (!node) return;
inorder(node->left, k, count, result);
if (++count == k) { result = node->val; return; }
inorder(node->right, k, count, result);
}
};
Time: O(H + k) where H is height. Space: O(H) for recursion stack.
Validate BST (LC 98) — Inorder Approach
class Solution {
TreeNode* prev = nullptr;
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
if (!isValidBST(root->left)) return false;
if (prev && root->val <= prev->val) return false;
prev = root;
return isValidBST(root->right);
}
};
Each visited value must be strictly greater than the previous in inorder sequence.
Time: O(n). Space: O(H).
Preorder Can Uniquely Reconstruct a BST
For a general binary tree, you need two traversals (e.g., preorder + inorder) to reconstruct the tree. For a BST, preorder alone is enough.
Why? The BST property tells us where the split is — we don't need inorder to find it. Every value less than the root goes left, every value greater goes right.
Preorder of our BST: [20, 10, 5, 3, 7, 15, 17, 30, 35]
Step 1: Root = 20
Values < 20: [10, 5, 3, 7, 15, 17] -> left subtree
Values > 20: [30, 35] -> right subtree
Step 2: Left subtree, Root = 10
Values < 10: [5, 3, 7] -> left
Values > 10: [15, 17] -> right
... and so on recursively.
Construct BST from Preorder (LC 1008)
The optimal approach uses an upper-bound technique — O(n) time:
class Solution {
int idx = 0;
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
return build(preorder, INT_MAX);
}
private:
TreeNode* build(vector<int>& preorder, int upperBound) {
if (idx == (int)preorder.size() || preorder[idx] > upperBound)
return nullptr;
int val = preorder[idx++];
TreeNode* node = new TreeNode(val);
node->left = build(preorder, val); // left values must be < val
node->right = build(preorder, upperBound); // right values must be < parent's bound
return node;
}
};
Time: O(n) — each node visited once. Space: O(H).
Postorder in BST — Delete / Free Safely
Same idea as general binary trees: process children before parent. In a BST this is used for safe deletion of the entire tree and for bottom-up computations like checking if a subtree is a valid BST with range tracking.
BST Search — O(H) Instead of O(n)
In a general binary tree, finding a value requires visiting every node — O(n). The BST property lets us eliminate half the tree at each step, like binary search.
TreeNode* search(TreeNode* root, int target) {
while (root) {
if (target == root->val) return root;
root = (target < root->val) ? root->left : root->right;
}
return nullptr; // not found
}
Time: O(H) — which is O(log n) for balanced BSTs, O(n) for skewed.
BST Insert — Always Becomes a Leaf
TreeNode* insert(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
BST Delete (LC 450) — Three Cases
Case 1: Node is a leaf → just remove it.
Case 2: Node has one child → replace node with that child.
Case 3: Node has two children → replace with inorder successor
(smallest in right subtree),
then delete that successor.
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
// Found the node to delete
if (!root->left) return root->right; // case 1 & 2
if (!root->right) return root->left; // case 2
// Case 3: find inorder successor (smallest in right subtree)
TreeNode* successor = root->right;
while (successor->left) successor = successor->left;
root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
}
return root;
}
};
Time: O(H). Space: O(H).
Lowest Common Ancestor in BST (LC 235) — O(H) Not O(n)
In a general binary tree, LCA requires visiting potentially all nodes — O(n). In a BST, the sorted property gives us a direct path:
If both values < node → LCA is in the left subtree
If both values > node → LCA is in the right subtree
Otherwise → current node IS the LCA (split point)
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root) {
if (p->val < root->val && q->val < root->val)
root = root->left;
else if (p->val > root->val && q->val > root->val)
root = root->right;
else
return root; // split point = LCA
}
return nullptr;
}
Time: O(H). Space: O(1).
Inorder Successor / Predecessor — O(H)
Another operation that the BST property makes efficient.
// Inorder successor: smallest node greater than the given node
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* successor = nullptr;
while (root) {
if (p->val < root->val) {
successor = root; // this could be it
root = root->left; // but look for something smaller
} else {
root = root->right; // need something bigger
}
}
return successor;
}
Time: O(H). Space: O(1).
How Traversals Change: Binary Tree vs BST
| Operation | Binary Tree | BST |
|---|---|---|
| Inorder result | Arbitrary order | Sorted order |
| Find a value | O(n) — must check all | O(H) — binary search path |
| Kth smallest | O(n) sort or heap | O(H + k) — inorder early stop |
| Validate structure | N/A | O(n) — inorder check prev < curr |
| Reconstruct from preorder | Need inorder too | Preorder alone suffices |
| LCA | O(n) — postorder | O(H) — follow BST path |
| Successor / Predecessor | O(n) | O(H) |
| Insert | Ambiguous (where?) | O(H) — BST property decides |
| Delete | Complex (no ordering) | O(H) — inorder successor swap |
Key takeaway: The BST property turns many O(n) tree operations into O(H) path operations. For a balanced BST, H = O(log n), making these operations logarithmic. For a skewed BST (essentially a linked list), H = O(n) and you lose the advantage — which is why self-balancing BSTs (AVL, Red-Black) exist.
BST-Specific Classic Problems
| # | Problem | Key Idea | LC |
|---|---|---|---|
| 1 | Validate BST | Inorder: each val > prev | 98 |
| 2 | Kth Smallest Element | Inorder early stop at k | 230 |
| 3 | LCA of BST | Follow split point | 235 |
| 4 | Delete Node in BST | 3 cases, inorder successor | 450 |
| 5 | Convert Sorted Array to BST | Pick mid as root, recurse | 108 |
| 6 | BST from Preorder | Upper-bound technique | 1008 |
| 7 | Inorder Successor in BST | Track last left turn | 285 |
| 8 | Two Sum IV (BST) | Inorder + two pointers | 653 |
| 9 | Recover BST (two swapped nodes) | Inorder finds the two violations | 99 |
| 10 | Trim BST to range [lo, hi] | Recurse, prune out-of-range | 669 |