Tree traversals are one of the first things we learn in data structures — but they’re often taught only at a surface level: as different ways to “walk” a tree. What’s rarely emphasized is this:
Table of Contents
A Quick Refresher
Given a binary tree, the three primary depth-first traversals are:
| Traversal | Order |
|---|---|
| Preorder | Root → Left → Right |
| Inorder | Left → Root → Right |
| Postorder | Left → Right → Root |
Preorder Traversal
I give you control first.
Key Idea: Root Comes First
Preorder is the only traversal that visits the root before anything else. This gives you immediate access to the “leader” of any subtree, which has deep implications.
What Makes It Special?
- Top-down construction: You can build or clone a tree from its root downwards. As you visit a node, you immediately create it and then recursively build its left and right children.
- Serialization: Preorder enables full tree serialization (with null markers for empty children), where each node is recorded before its structure. This order makes deserialization (reconstruction) natural — the first element is the root, then comes its left and right trees in order.
- Prefix notation (Polish notation): In expression trees, preorder directly maps to prefix expressions like + * 3 4 5 — evaluate the operator before operands.
- Control delegation : Useful when you want to perform actions on a node before its children — e.g., setting flags, copying data, creating structure, logging access.
Use Cases:
- Cloning or copying trees
- Serializing and deserializing trees
- Traversing a file system (e.g., printing folder names before their contents)
- Evaluating or printing expressions in prefix notation
- Assigning unique IDs top-down
Mental Model:
Here’s the leader. Now go handle the subordinates.
Inorder Traversal
I reveal order.
Key Idea: Root is the dividing point
Inorder uniquely positions the root between its left and right subtrees. It reveals a natural, balanced view of the tree.
What Makes It Special?
- Sorted output from Binary Search Trees (BSTs): In a BST, an inorder traversal produces a sorted sequence of values. This is the most powerful property of inorder traversal.
- Structure-neutral traversal: Inorder doesn’t depend on where the root is — it reflects the natural ordering of elements in a binary search space.
- Expression tree mapping to infix notation: In arithmetic expression trees, inorder yields the “human-style” expression: 3 + (4 * 5). It gives you infix notation, matching standard math syntax.
- Tree reconstruction aid: When combined with preorder or postorder, inorder allows full reconstruction of a binary tree. It tells you how left and right subtrees are arranged around each root.
Use Cases:
- Getting sorted data from BSTs
- Checking BST validity
- Printing expressions in human-readable infix format
- Splitting tree structure around a pivot
- Supporting reconstruction from preorder/inorder or postorder/inorder
Mental Model:
Let me understand the context on both sides before I act.
Postorder Traversal
I finish everything before you touch me.
Key Idea: Root Comes Last
Postorder defers visiting the root until both its children have been processed. This enables true bottom-up computation, where all dependencies are resolved before the node itself.
What Makes It Special?
- Safe deletion of trees: You can delete a tree safely using postorder — child nodes are deleted before their parent, preventing dangling references.
- Expression evaluation: In expression trees, postorder maps directly to postfix notation (Reverse Polish), which is stack-friendly and easy to evaluate without recursion.
- Dynamic Programming on trees: Many tree DP problems require processing children first — e.g., computing height, size, or max path sum. Postorder is perfect here: it gathers full results from subtrees before acting.
- Collect-then-act pattern: Whenever a task requires you to aggregate, combine, or summarize child data before processing the parent — postorder is the go-to.
Use Cases:
- Evaluating arithmetic expressions (postfix)
- Deleting/freeing memory of trees
- Tree dynamic programming
- Computing properties that depend on full subtrees
- Aggregation tasks (e.g., total subtree sum, size, height)
Mental Model
Don’t touch me until you’ve figured out all my dependencies.
Deep Comparison Table
| Feature | Preorder (Root-L-R) | Inorder (L-Root-R) | Postorder (L-R-Root) |
|---|---|---|---|
| Root Position | First | Middle | Last |
| Suited for | Construction, Cloning, Prefix | BST Traversal, Infix Output | Evaluation, Deletion, DP |
| Output in BST | Unordered | Sorted | Unordered |
| Tree Reconstruction | with nulls or inorder | not alone | with nulls or inorder |
| Expression Tree Mapping | Prefix | Infix | Postfix |
| Build Direction | Top-down | Balanced | Bottom-up |
| Used For Serialization | Common | Not suitable | with care) |
| Control Pattern | “Act before exploring” | “Explore both sides first” | “Act after everything else” |
| Works well with DP? | Not ideal | Not ideal | Best fit |
When to Choose Each Traversal
| Traversal | When to Use It (in real problems) |
|---|---|
| Preorder | When the root node controls the behavior of its subtree (e.g., serialization, cloning, path tracking) |
| Inorder | When you need to preserve ordering (e.g., sorted values from a BST, Kth smallest element) |
| Postorder | When child results must be fully known before acting on a node (e.g., tree DP, subtree aggregation) |
Practice
Cloning a Binary Tree
Cloning a binary tree means creating a new tree that is an exact, deep copy of the original tree.
- Every node in the new tree has the same value as the corresponding node in the original tree.
- The structure (how nodes are connected) is exactly the same.
- But the new tree is fully independent — it does not share any memory or pointers with the original tree.
Logic
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def clone_tree(node):
if not node:
return None
# Create a new node with the same value
new_node = TreeNode(node.val)
# Recursively clone left and right subtrees
new_node.left = clone_tree(node.left)
new_node.right = clone_tree(node.right)
return new_nodeImplementation
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def cloneTree(root: TreeNode) -> TreeNode:
if not root:
return None
new_root = TreeNode(root.val)
new_root.left = cloneTree(root.left)
new_root.right = cloneTree(root.right)
return new_root
# Helper function to print preorder traversal (for quick check)
def preorder(node):
if not node:
print("#", end=" ")
return
print(node.val, end=" ")
preorder(node.left)
preorder(node.right)
# ----------------------------
# Input Binary Tree
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)
# Clone the tree
cloned_root = cloneTree(root)
# Verify both trees
print("Original Tree (Preorder):")
preorder(root)
print("\nCloned Tree (Preorder):")
preorder(cloned_root)
print()Why not postorder or inorder?
Traversal order only affects when you visit nodes, not what you do with them. So technically, all of these can clone. But the cleanest and most intuitive for cloning is preorder, because:
- You create a node before dealing with its children.
- It matches natural recursion in top-down tree building.
Pre-order naturally fit for cloning, as we create the parent node before you try to attach its children.
Inorder
- You’d try to process the left subtree before the current node even exists.
- But you can’t attach children to a parent that hasn’t been created yet.
Postorder
- You build subtrees before the parent.
- Again, you can’t attach subtrees until the parent exists.
- You’d have to delay or store subtree clones temporarily, making it more complex and unnatural for cloning.
Serialize and Deserialize a Binary Tree
Serialization: Turning a Tree into Data. Serialization is the process of converting a binary tree structure into a linear string or list that can be:
- Stored in a file or database
- Sent over a network
- Copied between systems
You’re flattening the tree into a format that contains all the information necessary to rebuild it later.
Deserialization: Turning Data Back into a Tree. Deserialization is the reverse process: taking the serialized string/list and reconstructing the original binary tree structure in memory.
Preorder + null
Example
1
/ \
2 3
/ \
4 5
Serialization (Preorder with nulls) "1 2 # # 3 4 # # 5 # #"# represents null (None)
Logic
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Codec:
def serialize(self, root):
def dfs(node):
if not node:
result.append('#')
return
result.append(str(node.val))
dfs(node.left)
dfs(node.right)
result = []
dfs(root)
return ' '.join(result)
def deserialize(self, data):
def helper():
val = next(values)
if val == '#':
return None
node = TreeNode(int(val))
node.left = helper()
node.right = helper()
return node
values = iter(data.split())
return helper()- iter() allows recursion to consume values sequentially using next(), without worrying about an index.
- data.split(), to separate string by ” “
Shorthand version for serialization
def serialize(self, root):
if not root:
return '#'
return str(root.val) + ' ' + self.serialize(root.left) + ' ' + self.serialize(root.right)Input
# 👇 Example usage:
# Build a simple tree manually:
# 1
# / \
# 2 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
codec = Codec()
# Serialize the tree
s = codec.serialize(root)
print("Serialized:", s)
# Deserialize it back to tree
new_root = codec.deserialize(s)
print("Deserialized root value:", new_root.val)
'''
Output
Serialized: 1 2 # # 3 # #
Deserialized root value: 1
'''Inorder
Inorder + null
- Does NOT uniquely define a binary tree!
- Many different trees can give the same inorder traversal.
Case 1
1
/ \
2 3
Inorder with nulls = # 2 # 1 # 3 #
Case 2
2
\
1
\
3
Inorder with nulls = # 2 # 1 # 3 #Postorder + null
- Postorder + nulls works perfectly, just like preorder.
- But it requires you to build the tree backward, making it trickier to implement.
- That’s why preorder is more popular in real-world serialization.
code
class CodecPostorder:
def serialize(self, root):
if not root:
return '#'
return self.serialize(root.left) + ' ' + self.serialize(root.right) + ' ' + str(root.val)
def deserialize(self, data):
def helper(vals):
val = vals.pop() # pop from the end (root comes last)
if val == '#':
return None
node = TreeNode(int(val))
node.right = helper(vals) # important: build right first
node.left = helper(vals)
return node
vals = data.split()
return helper(vals)Level order, BFS
from collections import deque
class CodecBFS:
def serialize(self, root):
if not root:
return ""
res = []
q = deque([root])
while q:
node = q.popleft()
if node:
res.append(str(node.val))
q.append(node.left)
q.append(node.right)
else:
res.append("#")
# remove trailing "#" (not needed for reconstruction)
while res and res[-1] == "#":
res.pop()
return " ".join(res)
def deserialize(self, data):
if not data:
return None
vals = data.split()
root = TreeNode(int(vals[0]))
q = deque([root])
i = 1
while q and i < len(vals):
node = q.popleft()
# Left child
if vals[i] != "#":
node.left = TreeNode(int(vals[i]))
q.append(node.left)
i += 1
# Right child
if i < len(vals) and vals[i] != "#":
node.right = TreeNode(int(vals[i]))
q.append(node.right)
i += 1
return rootSummary
| Traversal | Serialized (same tree) | Can Deserialize? | Notes |
|---|---|---|---|
| Preorder | 1 2 # # 3 4 # # 5 # # | ✅ Yes | Root comes first, natural recursion |
| Postorder | # # 2 # # 4 # # 5 3 1 | ✅ Yes | Root comes last, need reverse processing |
| Inorder | # 2 # 1 # 4 # 3 # 5 # | ❌ No | Ambiguous without extra info |
| BFS | 1 2 3 # # 4 5 # # # # (trimmed) | ✅ Yes | Easy with queue |
Contraction
If one traversal (like preorder) isn’t enough to rebuild a tree normally… Then how can we serialize and deserialize using just preorder?
Why do we need two traversals to reconstruct a tree, but only one for serialization?
- Serialization adds null markers (like #), which preserve the entire structure of the tree — not just the node values.
- That’s why one traversal + nulls is enough for full reconstruction.
Summary
| Type | Do We Know Structure? | Extra Info Needed? |
|---|---|---|
| Preorder alone | ❌ No | Needs inorder/postorder |
Preorder + nulls (#) | ✅ Yes | No other info needed |
| Inorder alone | ❌ No | Needs preorder/postorder |
| Inorder + nulls | ❌ No | Still ambiguous |
| Postorder alone | ❌ No | Needs inorder/preorder |
Postorder + nulls (#) | ✅ Yes | No other info needed |
In postorder, root comes last:
- So you must process the list in reverse
- While deserializing:
- Start from the end
- Build right subtree first, then left subtree
- This reversed recursion can confuse people if they’re used to top-down tree building.
Conclusion
- Postorder + null markers (#) is enough to serialize and deserialize a binary tree — but it’s more complex to implement than preorder.
- We use Preorder + null because it gives the root first, and with nulls, preserves full structure. It’s naturally fits
Prefix Expression (Polish Notation)
If you build an expression tree like:
+
/ \
* 5
/ \
3 4The preorder traversal gives you the prefix expression: + * 3 4 5
Root-to-Leaf Path Tracking
In problems where you need to track paths from root to leaves, you usually start from the root and build the path as you recurse.
As you traverse the tree top-down (usually using preorder traversal), you maintain a path list or string that represents the nodes you’ve visited so far. When you reach a leaf node, you finalize the path and store or return it.
Logic
def dfs(node, path, result):
if not node:
return
path.append(node.val)
# If it's a leaf, save the path
if not node.left and not node.right:
result.append(list(path)) # make a copy
else:
dfs(node.left, path, result)
dfs(node.right, path, result)
path.pop() # backtrack
- Traverse the tree
- Keep a running list of the path so far
- On reaching a leaf, record the current path
- Backtrack to explore other paths
- When you return from a child, you must remove its contribution to the current path.
- Without path.pop() or re-creating the path, the path would “leak” and be incorrect.
Implementation
def binaryTreePathsList(root):
result = []
def dfs(node, path):
if node:
# Add current node value
path.append(node.val)
# Leaf node → save path copy
if not node.left and not node.right:
result.append(list(path))
else:
dfs(node.left, path)
dfs(node.right, path)
# Backtrack
path.pop()
dfs(root, [])
return result
# Test
root = TreeNode(1)
root.left = TreeNode(2, None, TreeNode(5))
root.right = TreeNode(3)
'''
1
/ \
2 3
\
5
'''
print(binaryTreePathsList(root))
# Output: [[1, 2, 5], [1, 3]]Common problem
Why Use Preorder Traversal?
Preorder fits naturally here because:
- You need to process the current node first (add it to the path),
- Then recursively explore its children,
- And only at leaf nodes, decide to save the full path.
- This makes it a top-down traversal pattern.
Kth Smallest Element in BST
Inorder natually gives values in sorted form if it BST
5
/ \
3 7
/ \ \
2 4 8
Inorder : [2, 3, 4, 5, 7, 8] ✅ SortedIf it’s just a binary tree (no BST property), inorder won’t necessarily be sorted.
5
/ \
9 2
Inorder: [9, 5, 2] → Not sorted.So, we can use inorder, but we should’nt traversel entrire tree. We should stop it when we got required values
Logic
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kthSmallest(self, root: TreeNode, k: int) -> int:
self.k = k
self.result = None
def inorder(node):
if not node or self.result is not None:
return
inorder(node.left)
self.k -= 1
if self.k == 0:
self.result = node.val
return
inorder(node.right)
inorder(root)
return self.result
root = TreeNode(3)
root.left = TreeNode(1)
root.left.right = TreeNode(2)
root.right = TreeNode(4)
print(Solution().kthSmallest(root, 1)) # 1
print(Solution().kthSmallest(root, 2)) # 2
print(Solution().kthSmallest(root, 3)) # 3
print(Solution().kthSmallest(root, 4)) # 4
Validate BST
Method 1: Inorder Traversal (Sorted Check)
- Key idea: If you do an inorder traversal of a valid BST, you get a strictly increasing sequence.
- Why it works:
- Inorder visits: Left → Root → Right
- which, in a BST, naturally produces values in ascending order.
def isValidBST(root):
prev = None
def inorder(node):
nonlocal prev
if not node:
return True
if not inorder(node.left): # Visit left
return False
if prev is not None and node.val <= prev: # Check sorted property
return False
prev = node.val
return inorder(node.right) # Visit right
return inorder(root)- Time complexity: O(n)
- Space complexity: O(h) (stack space, h = tree height)
Method 2
def isValidBST(root):
def validate(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root, float('-inf'), float('inf'))
- Time complexity: O(n)
- Space complexity: O(h)
Common Mistake to Avoid : Only checking immediate children is wrong.
10
/ \
5 15
/ \
6 20
At first glance:
- 6 < 15 ✅
- 20 > 15 ✅
But 6 is in the right subtree of 10, so it must be > 10 — rule is broken.
Range-check method catches this; naive child check won’t.
Build a Tree from traversal
For building back a tree from traversal we need
- preorder + inorder
- postorder + inorder
Inorder
inorder = [ Left Subtree Nodes | Root | Right Subtree Nodes ]Finding index(mid) of root of inorder will give
- Left subtree size = mid
- Right subtree size = len(inorder) – mid – 1
mid = inorder.index(root_val), The mid from inorder.index(root) always gives you the size of the left subtree.
Case 1 — Preorder
Preorder = Root | Left Subtree | Right Subtree- Root is always the first element (preorder[0]).
- The left subtree starts immediately after the root at index 1.
- Since left subtree size = mid, it takes mid elements:
Left sub tree
- starting index = 1
- end index = starting index+size = 1+m
Right sub tree
- strarting from 1+m, till last
preorder[1 : 1+mid] # left subtree
preorder[1+mid : ] # right subtreeCase 2 — Postorder
Postorder = Left Subtree | Right Subtree | Root- Root is always the last element (postorder[-1]).
- The left subtree starts at index 0 in postorder and takes mid elements:
postorder[:mid] # left subtree
postorder[mid:-1] # right subtreeNo matter preorder or postorder:
- mid = number of nodes in the left subtree
- In Preorder, left subtree starts at index 1.
- In Postorder, left subtree starts at index 0.
Example 1: Preorder + Inorder
Preorder: [3, 9, 20, 15, 7]
Inorder: [9, 3, 15, 20, 7]Steps to solve
- Root = 3 (first in preorder)
- In inorder, 3 is at index 1 → left subtree size = 1
- Left preorder = [9]
- Right preorder = [20, 15, 7]
3
/ \
9 20
/ \
15 7Example 2 — Postorder + Inorder
Postorder: [9, 15, 7, 20, 3]
Inorder: [9, 3, 15, 20, 7]Steps to solve
- Root = 3 (last in postorder)
- In inorder, 3 is at index 1 → left size = 1
- Left postorder = [9]
- Right postorder = [15, 7, 20]
3
/ \
9 20
/ \
15 7Examples
Preorder: [1, 2, 4, 5, 3]
Inorder: [4, 2, 5, 1, 3]
1
/ \
2 3
/ \
4 5
----------------------------------------------------------------------------------------------
Postorder: [4, 5, 2, 3, 1]
Inorder: [4, 2, 5, 1, 3]
1
/ \
2 3
/ \
4 5
----------------------------------------------------------------------------------------------
Preorder: [10, 5, 1, 7, 40, 50]
Inorder: [1, 5, 7, 10, 40, 50]
10
/ \
5 40
/ \ \
1 7 50
----------------------------------------------------------------------------------------------
Postorder: [1, 7, 5, 50, 40, 10]
Inorder: [1, 5, 7, 10, 40, 50]
10
/ \
5 40
/ \ \
1 7 50
----------------------------------------------------------------------------------------------
Preorder: [8, 4, 2, 6, 12, 10, 14]
Inorder: [2, 4, 6, 8, 10, 12, 14]
8
/ \
4 12
/ \ / \
2 6 10 14Code: Preorder + Inorder
def buildTreePre(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = buildTreePre(preorder[1:1+mid], inorder[:mid])
root.right = buildTreePre(preorder[1+mid:], inorder[mid+1:])
return root
Code: Postorder + Inorder
def buildTreePost(postorder, inorder):
if not postorder or not inorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = buildTreePost(postorder[:mid], inorder[:mid])
root.right = buildTreePost(postorder[mid:-1], inorder[mid+1:])
return root
Where inorder(mid)?
we use inorder[:mid]) and inorder[mid+1:], leaving behind inorder[mid], as we already used that root. Now there role of it.
Problems
3 thoughts on “The Deep Power Behind Tree Traversals: Preorder, Inorder, Postorder”