In-order Tree Traversal — Sorted BST Visualized
Learn in-order traversal — left, root, right order, produces sorted output on BST, step-by-step visualizer and code.
Introduction
In-order traversal visits nodes in Left → Root → Right order (LNR). On a binary search tree, in-order produces sorted ascending values.
Quick index
1. Traversal order
For tree [4, 2, 6, 1, 3, 5, 7]:
In-order: 1 → 2 → 3 → 4 → 5 → 6 → 7
Visit left subtree, then root, then right subtree.
2. Interactive visualizer
In-order Traversal — Left → Root → Right
Visit root between subtrees — on a BST, produces sorted ascending order.
In-order: Left → Root → Right.
In-order traversal
| function inOrder(node) { | |
| if (!node) return | |
| inOrder(node.left) | |
| visit(node) | root middle |
| inOrder(node.right) | |
| } |
Left → Root → Right
Order
LNR
BST
Sorted
Time
O(n)
3. Full implementation
function inOrder(node, result = []) {
if (!node) return result
inOrder(node.left, result)
result.push(node.value) // visit root MIDDLE
inOrder(node.right, result)
return result
}
function inOrderIterative(root) {
const stack = [],
result = []
let cur = root
while (cur || stack.length) {
while (cur) {
stack.push(cur)
cur = cur.left
}
cur = stack.pop()
result.push(cur.value)
cur = cur.right
}
return result
}Function calls with output
// ── Demo calls — output shown on the right ──
inOrder(root) // → [1, 2, 3, 4, 5, 6, 7]
inOrderIterative(root) // → [1, 2, 3, 4, 5, 6, 7]
// on a BST, in-order always returns sorted ascending:
inOrder(bstRoot) // → [1, 3, 4, 6, 7, 8, 10, 13, 14]4. BST sorted output
On a BST, in-order always yields ascending sorted order — this is how you print a BST's values in order without a separate sort step.
Summary
In-order = root between subtrees — the traversal that sorts a BST.
Next reads: Post-order Traversal · Binary Search Trees
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime