Binary Trees — Visual Learning

Inorder Traversal —
Left, Root, Right — always sorted on a BST.

Inorder traversal visits the left subtree, then the root, then the right subtree — and on a binary search tree that order always comes out sorted. It's the traversal every other one gets compared to. Watch the recursion dive all the way left before it prints anything on LearnBug and the "why sorted" question answers itself.

O(n)Time complexity
O(h)Space (call stack)
PythonLanguage

What is Inorder Traversal?

Visit the left subtree, then the current node, then the right subtree — recursively. For the tree 4(2(1,3),6) this visits 1, 2, 3, 4, 6. Because a BST keeps everything smaller than a node in its left subtree and everything larger in its right subtree, Left→Root→Right always produces values in ascending order.

Why visualization helps

The recursion doesn't print anything until it has gone as far left as possible — that "silent dive" is the part beginners lose track of on paper. On LearnBug you watch the current node highlight at every recursive call, including the calls that return without printing, so the dive and the backtrack are both visible instead of assumed.

YouTube — Inorder Traversal Explained Visually
📺 Drop your YouTube embed here
LearnBug — recursion diving left then backtracking
🖼 Add a LearnBug screenshot here
Three DFS Orders

Inorder vs preorder vs postorder

Inorder — L → Root → R ✓

Visits the root between its children. On a BST, this is the only order that comes out sorted — that's the whole point of this lesson.

Sorted on BSTO(n)

Preorder — Root → L → R

Visits the root first, before either child. Used to copy/serialize a tree, because the root is always recorded before its descendants.

SerializationO(n)

Postorder — L → R → Root

Visits the root last. Used when children must be processed before the parent — deleting a tree, or evaluating an expression tree.

Tree deletionO(n)
Walkthrough

Inorder traversal on 4(2(1,3), 6)

1

inorder(4) calls inorder(4.left) first — dives to node 2

Before node 4 prints anything, the call must fully resolve its left subtree. inorder(4) → inorder(2). Nothing has printed yet — this is the "silent dive."

4call 1
2call 2
1
3
6
Call stack: inorder(4) → inorder(2)  |  Output so far: []
2

inorder(2) dives further left to node 1 — a leaf with no left child

inorder(1.left) is None, so the recursion returns immediately. Node 1 prints — it's the first value in the output because it's the leftmost node in the whole tree.

1visit
2
3
4
6
Call stack: inorder(4) → inorder(2) → inorder(1)  |  Output: [1]
3

inorder(1) returns — control comes back to node 2, which now prints itself

With the left side of node 2 fully visited, inorder(2) prints 2, then calls inorder(2.right) which visits node 3.

1
2visit
3
4
6
Output: [1, 2, 3]  |  Node 2's subtree is fully resolved — control returns to node 4
4

inorder(4) prints 4, then dives right into node 6 — a leaf

Node 4's entire left subtree [1, 2, 3] is done, so it prints itself, then visits node 6, which has no children and prints immediately.

1
2
3
4visit
6
Output: [1, 2, 3, 4, 6] — sorted, without ever sorting

Return: [1, 2, 3, 4, 6] ✓ ascending order, straight from the BST shape

Python Code

Recursive and iterative inorder

PythonRecursive — O(n) time, O(h) space
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)   # dive left first
    result.append(node.val)      # visit root in the middle
    inorder(node.right, result)  # then right
PythonIterative — explicit stack, same O(n) / O(h)
def inorder_iterative(root):
    result, stack = [], []
    node = root
    while stack or node:
        while node:               # push all the way left
            stack.append(node)
            node = node.left
        node = stack.pop()        # backtrack — visit
        result.append(node.val)
        node = node.right         # then explore right
    return result

Complexity Notes

TimeO(n)Every node is visited exactly once
SpaceO(h)Call stack depth = tree height, O(log n) balanced, O(n) skewed
Why sorted?BST propertyLeft subtree < node < right subtree, at every node, recursively
On a plain binary treeNot sortedSorted output only holds for a valid BST — inorder itself doesn't sort anything

Frequently asked questions

Why does inorder traversal give sorted output on a BST?

A BST guarantees that at every node, everything in the left subtree is smaller and everything in the right subtree is larger. Left→Root→Right recursively visits "everything smaller", then "this value", then "everything larger" — which is exactly the definition of ascending order.

What if the tree isn't a BST?

Inorder traversal still visits Left → Root → Right, but without the BST ordering guarantee, the output is not sorted — it's just whatever order the tree happens to be shaped in. This is actually used as a BST validity check: run inorder and verify the output is strictly increasing.

How do I convert the recursive version to iterative?

Use an explicit stack to simulate the call stack: push nodes while going left, then when you can't go left anymore, pop, visit, and move right. See the second code block above — same O(n) time and O(h) space, no recursion limit risk on very deep trees.

What's the difference between preorder, inorder, and postorder?

All three visit every node exactly once with the same O(n) time — they only differ in when the current node is visited relative to its children: preorder visits it first (serialization), inorder visits it between children (BST sorted output), postorder visits it last (safe to delete children before the parent).

Watch the recursion dive left, then unwind

Paste any tree traversal into LearnBug and see every recursive call highlight on the tree.

Open Playground →

Related topics

Preorder Traversal — Root first →BST Search — using the same ordering →Level Order — BFS instead of DFS →BFS vs DFS — Interview →