Inorder Traversal of BST Produces Sorted Order - Inorder Traversal & Sorted Output | OneNoughtOne

Data Structures & AlgorithmsBST Inorder Traversal & Sorted Output

Inorder Traversal & Sorted Output

LevelIntermediate

Duration55 mins

TopicBST Inorder Traversal & Sorted Output

1 / 4

Inorder Traversal of BST Produces Sorted Order

The Hidden Symphony in Tree Structure

There exists a profound and beautiful relationship between Binary Search Trees and sorted sequences—one that reveals itself through a simple traversal pattern. When you walk through a BST using inorder traversal (left subtree, then root, then right subtree), something remarkable happens: the nodes appear in perfectly ascending order.

This isn't coincidental. It's an inevitable consequence of the BST property itself. Understanding this connection transforms how you think about BSTs—from mere search structures to dynamic, self-organizing sorted collections.

What You Will Learn

By the end of this page, you will understand why inorder traversal of a BST naturally produces sorted output. You'll see how the BST property guarantees this behavior, trace through examples that illuminate the pattern, and recognize why this property is foundational to countless BST applications.

Revisiting Inorder Traversal

Before we explore the sorted output property, let's ensure we have a crystal-clear understanding of inorder traversal itself.

Inorder traversal is one of the three fundamental depth-first traversal patterns for binary trees. The traversal follows a specific visitation order:

Recursively traverse the left subtree
Visit (process) the current node
Recursively traverse the right subtree

This pattern is often abbreviated as L-N-R (Left-Node-Right) or simply Left → Root → Right.

inorder_traversal.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def inorder_traversal(node):
    """
    Performs inorder traversal of a binary tree.
    For a BST, this will visit nodes in ascending order.
    
    Args:
        node: The root node of the tree/subtree to traverse
    
    Time Complexity: O(n) - visits each node exactly once
    Space Complexity: O(h) - recursion stack depth equals tree height
    """
    if node is None:
        return
    
    # Step 1: Process entire left subtree first
    inorder_traversal(node.left)
    
    # Step 2: Visit (process) the current node
    print(node.value)  # Or: result.append(node.value)
    
    # Step 3: Process entire right subtree
    inorder_traversal(node.right)

The key insight:

In a general binary tree (without the BST property), inorder traversal simply visits nodes in a particular order determined by the tree's structure—there's no guarantee about the relationship between values.

But in a Binary Search Tree, inorder traversal gains an extraordinary property: it visits nodes in ascending sorted order. This isn't magic—it's a direct consequence of how the BST property constrains the tree's structure.

The BST Property Refresher

To understand why inorder traversal produces sorted output, we must revisit the BST property with precision:

For every node N in a Binary Search Tree:

All values in the left subtree of N are strictly less than N's value

All values in the right subtree of N are strictly greater than N's value

Note the critical word: all. This isn't just about immediate children—it applies to every descendant in the subtree. This recursive, all-encompassing property is what makes BSTs so powerful.

The 'All Descendants' Distinction

A common misconception is that the BST property only requires left.value < node.value < right.value for immediate children. This weaker definition breaks the sorted output guarantee. The true BST property requires that ALL nodes in the left subtree are smaller, and ALL nodes in the right subtree are larger.

Valid BST

•Every left descendant < ancestor
•Every right descendant > ancestor
•Property holds for ALL subtrees
•Inorder traversal = sorted order

Invalid BST

•Only checks immediate children
•Allows invalid values in subtrees
•Property may fail for deep nodes
•Inorder traversal ≠ sorted order

Visualizing the constraint:

Consider a node with value 50. The BST property means:

Its entire left subtree contains only values less than 50
Its entire right subtree contains only values greater than 50

This constraint propagates recursively. If 50's left child is 30, then 30's entire left subtree contains values less than 30 (and by extension, less than 50), while 30's right subtree contains values greater than 30 but still less than 50.

This nested constraint structure is precisely what creates the sorted output property.

Why Inorder Traversal Yields Sorted Output

Now we can see why inorder traversal produces sorted output. The argument is elegant and intuitive:

For any node N in the BST:

Before visiting N, inorder traversal first visits the entire left subtree
- By the BST property, every value in the left subtree is less than N
- Therefore, all these smaller values are output before N
When visiting N, we output N's value
- This value is greater than everything in the left subtree (already output)
- This value is less than everything in the right subtree (not yet output)
After visiting N, inorder traversal visits the entire right subtree
- By the BST property, every value in the right subtree is greater than N
- Therefore, all these larger values are output after N

The Core Insight

Inorder traversal visits left subtree → node → right subtree. The BST property ensures left subtree < node < right subtree. Therefore, inorder traversal visits: smaller values → current value → larger values. This is precisely what sorted order means!

The recursive argument:

This reasoning applies recursively to every node in the tree:

For the root: left subtree (all smaller) → root → right subtree (all larger)
For each subtree root: same pattern repeats
At every level, the L-N-R pattern respects the local sorted order

When you combine these local orderings, the global result is a complete sorted sequence. The BST structure has essentially "pre-sorted" the data—inorder traversal merely reveals this hidden order.

A Detailed Walk-Through Example

Let's trace through a complete example to see this property in action. Consider the following BST:

           50
          /  
        30    70
       /  \   /  
      20  40 60  80
     /
    10

This tree contains the values: 10, 20, 30, 40, 50, 60, 70, 80 (in sorted order, as we'll verify).

Inorder Traversal Step-by-Step Trace
Step	Current Action	Output So Far	Why This Order?
1	Start at 50, go left to 30	[]	Must visit left subtree first
2	At 30, go left to 20	[]	Must visit left subtree first
3	At 20, go left to 10	[]	Must visit left subtree first
4	At 10, left is null	[]	Left subtree empty
5	Visit 10 (no left child)	[10]	Smallest in this subtree
6	10's right is null, return to 20	[10]	Right subtree empty
7	Visit 20	[10, 20]	Left done, now process node
8	20's right is null, return to 30	[10, 20]	Right subtree empty
9	Visit 30	[10, 20, 30]	Left done, now process node
10	Go right to 40	[10, 20, 30]	Now visit right subtree
11	40 has no left, visit 40	[10, 20, 30, 40]	Left null, process node
12	40's right null, return to 50	[10, 20, 30, 40]	Right subtree empty
13	Visit 50	[10, 20, 30, 40, 50]	Left subtree done
14	Go right to 70	[10, 20, 30, 40, 50]	Now visit right subtree
15	At 70, go left to 60	[10, 20, 30, 40, 50]	Must visit left first
16	60 has no left, visit 60	[10, 20, 30, 40, 50, 60]	Left null, process node
17	60's right null, return to 70	[10, 20, 30, 40, 50, 60]	Right subtree empty
18	Visit 70	[10, 20, 30, 40, 50, 60, 70]	Left done, process node
19	Go right to 80	[10, 20, 30, 40, 50, 60, 70]	Now visit right subtree
20	80 has no left, visit 80	[10, 20, 30, 40, 50, 60, 70, 80]	Left null, process node
21	80's right null, done	[10, 20, 30, 40, 50, 60, 70, 80]	Traversal complete

Observation:

The final output is [10, 20, 30, 40, 50, 60, 70, 80]—a perfectly sorted sequence! Notice how each node is visited only after all smaller nodes (its left subtree and all ancestors' left subtrees) and before all larger nodes (its right subtree and all ancestors' right subtrees).

Every Node at the Right Time

The beauty of this process is that every node appears in the output at exactly the right moment—after all smaller values and before all larger values. The BST structure encodes the sorted relationships, and inorder traversal simply reads them out.

The First and Last Elements

The sorted output property reveals important truths about the minimum and maximum elements in a BST:

Finding the Minimum:

The first element visited by inorder traversal is the minimum value in the BST
This node is found by following left pointers from the root until we reach a node with no left child
Why? Because inorder traversal exhausts all left subtrees before visiting any node

Finding the Maximum:

The last element visited by inorder traversal is the maximum value in the BST
This node is found by following right pointers from the root until we reach a node with no right child
Why? Because inorder traversal visits all right subtrees after visiting each node

find_min_max.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def find_minimum(node):
    """
    Find the minimum value in a BST.
    
    The minimum is the leftmost node in the tree - the same node
    that inorder traversal would visit first.
    
    Time Complexity: O(h) where h is the height of the tree
    Space Complexity: O(1)
    """
    if node is None:
        return None
    
    current = node
    # Keep going left until we can't go anymore
    while current.left is not None:
        current = current.left
    
    return current.value
 
 
def find_maximum(node):
    """
    Find the maximum value in a BST.
    
    The maximum is the rightmost node in the tree - the same node
    that inorder traversal would visit last.
    
    Time Complexity: O(h) where h is the height of the tree
    Space Complexity: O(1)
    """
    if node is None:
        return None
    
    current = node
    # Keep going right until we can't go anymore
    while current.right is not None:
        current = current.right
    
    return current.value
 
 
# These operations directly leverage the sorted output property!
# Minimum = first in sorted order = leftmost node
# Maximum = last in sorted order = rightmost node

The connection to sorted arrays:

This is analogous to a sorted array where:

array[0] is the minimum (first element)
array[n-1] is the maximum (last element)

The BST provides similar "sorted" access, but with the added ability to efficiently insert and delete elements while maintaining order—something sorted arrays struggle with.

Inorder Successor and Predecessor

The sorted output property gives meaning to two critical concepts:

Inorder Successor: The node that would be visited immediately after a given node in inorder traversal. In sorted terms, this is the smallest value greater than the node's value (the "next" element).

Inorder Predecessor: The node that would be visited immediately before a given node in inorder traversal. In sorted terms, this is the largest value less than the node's value (the "previous" element).

Finding Inorder Successor

•Case 1: Node has a right subtree → The successor is the minimum node in the right subtree (leftmost node in right subtree)
•Case 2: Node has no right subtree → The successor is the lowest ancestor for which this node is in the left subtree (walk up until we came from the left)

Finding Inorder Predecessor

•Case 1: Node has a left subtree → The predecessor is the maximum node in the left subtree (rightmost node in left subtree)
•Case 2: Node has no left subtree → The predecessor is the lowest ancestor for which this node is in the right subtree (walk up until we came from the right)

These concepts are fundamental to BST operations, particularly deletion. When deleting a node with two children, we replace it with either its inorder successor or predecessor—maintaining the sorted order property.

Why This Matters for Deletion

When you delete a node with two children from a BST, replacing it with the inorder successor (or predecessor) ensures the BST property is maintained. The successor is the smallest value that's still greater than all values in the left subtree—making it a valid replacement.

The Elegance of This Property

Step back and appreciate what we've discovered:

A BST is a sorted collection in disguise.

Unlike arrays where sorting requires explicit comparison and rearrangement, a BST maintains sorted order implicitly through its structure. Every insertion automatically places elements in their sorted position. Every traversal can reveal the sorted sequence without any sorting algorithm.

This dual nature—a tree structure that encodes a sorted sequence—is what makes BSTs so versatile:

BST: Combining Tree and Sorted Sequence Benefits
Capability	How BST Provides It	Complexity
Find minimum	Go leftmost	O(h)
Find maximum	Go rightmost	O(h)
Find any element	Binary search traversal	O(h)
Insert while maintaining order	Find position, attach	O(h)
Delete while maintaining order	Use successor/predecessor	O(h)
Get all elements in sorted order	Inorder traversal	O(n)
Find k-th smallest element	Inorder traversal to k	O(k + h)
Find elements in range	Modified inorder	O(h + k)

The trade-off with arrays:

Compare this to a sorted array:

Arrays give O(1) access to any position but O(n) insertion/deletion
BSTs give O(h) access to any element with O(h) insertion/deletion

When h = O(log n) (balanced tree), BSTs excel at dynamic scenarios where data changes frequently. When data is static, sorted arrays with binary search may be preferable for their cache efficiency and simpler implementation.

Summary: The Sorted Output Property

We've established one of the most fundamental properties of Binary Search Trees. Let's consolidate what we've learned:

Key Takeaways

•Inorder traversal (L-N-R) of a BST produces elements in ascending sorted order — This is an inevitable consequence of the BST property, not a coincidence.
•The BST property ensures left < node < right for ALL descendants — This recursive constraint is what guarantees sorted output, not just immediate children.
•Minimum is the leftmost node; maximum is the rightmost — The first and last elements in sorted order are found by following left/right pointers to their ends.
•Inorder successor/predecessor define 'next' and 'previous' in sorted order — These concepts are crucial for BST deletion and range operations.
•A BST is a dynamic sorted collection — It maintains sorted order through structure, enabling efficient insertion and deletion unlike static sorted arrays.
•Understanding this property is foundational — Almost every BST algorithm leverages the sorted output property in some way.

What's next:

Now that we understand what the sorted output property is, the next page provides a rigorous proof of why it holds. We'll use invariant thinking to formally establish this property, building the kind of deep understanding that transfers to other data structure proofs.

Page Complete

You now understand the fundamental connection between BST structure and sorted sequences. Inorder traversal reveals the hidden sorted order encoded in every BST. Next, we'll prove this property rigorously using invariant-based reasoning.

1 / 4

Loading learning content...

Data Structures & AlgorithmsBST Inorder Traversal & Sorted Output

Inorder Traversal & Sorted Output

LevelIntermediate

Duration55 mins

TopicBST Inorder Traversal & Sorted Output

1 / 4

Inorder Traversal of BST Produces Sorted Order

The Hidden Symphony in Tree Structure

What You Will Learn

Revisiting Inorder Traversal

Before we explore the sorted output property, let's ensure we have a crystal-clear understanding of inorder traversal itself.

Inorder traversal is one of the three fundamental depth-first traversal patterns for binary trees. The traversal follows a specific visitation order:

Recursively traverse the left subtree
Visit (process) the current node
Recursively traverse the right subtree

This pattern is often abbreviated as L-N-R (Left-Node-Right) or simply Left → Root → Right.

inorder_traversal.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def inorder_traversal(node):
    """
    Performs inorder traversal of a binary tree.
    For a BST, this will visit nodes in ascending order.
    
    Args:
        node: The root node of the tree/subtree to traverse
    
    Time Complexity: O(n) - visits each node exactly once
    Space Complexity: O(h) - recursion stack depth equals tree height
    """
    if node is None:
        return
    
    # Step 1: Process entire left subtree first
    inorder_traversal(node.left)
    
    # Step 2: Visit (process) the current node
    print(node.value)  # Or: result.append(node.value)
    
    # Step 3: Process entire right subtree
    inorder_traversal(node.right)

The key insight:

The BST Property Refresher

To understand why inorder traversal produces sorted output, we must revisit the BST property with precision:

For every node N in a Binary Search Tree:

All values in the left subtree of N are strictly less than N's value

All values in the right subtree of N are strictly greater than N's value

Note the critical word: all. This isn't just about immediate children—it applies to every descendant in the subtree. This recursive, all-encompassing property is what makes BSTs so powerful.

The 'All Descendants' Distinction

Valid BST

•Every left descendant < ancestor
•Every right descendant > ancestor
•Property holds for ALL subtrees
•Inorder traversal = sorted order

Invalid BST

•Only checks immediate children
•Allows invalid values in subtrees
•Property may fail for deep nodes
•Inorder traversal ≠ sorted order

Visualizing the constraint:

Consider a node with value 50. The BST property means:

Its entire left subtree contains only values less than 50
Its entire right subtree contains only values greater than 50

This nested constraint structure is precisely what creates the sorted output property.

Why Inorder Traversal Yields Sorted Output

Now we can see why inorder traversal produces sorted output. The argument is elegant and intuitive:

For any node N in the BST:

Before visiting N, inorder traversal first visits the entire left subtree
- By the BST property, every value in the left subtree is less than N
- Therefore, all these smaller values are output before N
When visiting N, we output N's value
- This value is greater than everything in the left subtree (already output)
- This value is less than everything in the right subtree (not yet output)
After visiting N, inorder traversal visits the entire right subtree
- By the BST property, every value in the right subtree is greater than N
- Therefore, all these larger values are output after N

The Core Insight

The recursive argument:

This reasoning applies recursively to every node in the tree:

For the root: left subtree (all smaller) → root → right subtree (all larger)
For each subtree root: same pattern repeats
At every level, the L-N-R pattern respects the local sorted order

When you combine these local orderings, the global result is a complete sorted sequence. The BST structure has essentially "pre-sorted" the data—inorder traversal merely reveals this hidden order.

A Detailed Walk-Through Example

Let's trace through a complete example to see this property in action. Consider the following BST:

           50
          /  
        30    70
       /  \   /  
      20  40 60  80
     /
    10

This tree contains the values: 10, 20, 30, 40, 50, 60, 70, 80 (in sorted order, as we'll verify).

Inorder Traversal Step-by-Step Trace
Step	Current Action	Output So Far	Why This Order?
1	Start at 50, go left to 30	[]	Must visit left subtree first
2	At 30, go left to 20	[]	Must visit left subtree first
3	At 20, go left to 10	[]	Must visit left subtree first
4	At 10, left is null	[]	Left subtree empty
5	Visit 10 (no left child)	[10]	Smallest in this subtree
6	10's right is null, return to 20	[10]	Right subtree empty
7	Visit 20	[10, 20]	Left done, now process node
8	20's right is null, return to 30	[10, 20]	Right subtree empty
9	Visit 30	[10, 20, 30]	Left done, now process node
10	Go right to 40	[10, 20, 30]	Now visit right subtree
11	40 has no left, visit 40	[10, 20, 30, 40]	Left null, process node
12	40's right null, return to 50	[10, 20, 30, 40]	Right subtree empty
13	Visit 50	[10, 20, 30, 40, 50]	Left subtree done
14	Go right to 70	[10, 20, 30, 40, 50]	Now visit right subtree
15	At 70, go left to 60	[10, 20, 30, 40, 50]	Must visit left first
16	60 has no left, visit 60	[10, 20, 30, 40, 50, 60]	Left null, process node
17	60's right null, return to 70	[10, 20, 30, 40, 50, 60]	Right subtree empty
18	Visit 70	[10, 20, 30, 40, 50, 60, 70]	Left done, process node
19	Go right to 80	[10, 20, 30, 40, 50, 60, 70]	Now visit right subtree
20	80 has no left, visit 80	[10, 20, 30, 40, 50, 60, 70, 80]	Left null, process node
21	80's right null, done	[10, 20, 30, 40, 50, 60, 70, 80]	Traversal complete

Observation:

Every Node at the Right Time

The First and Last Elements

The sorted output property reveals important truths about the minimum and maximum elements in a BST:

Finding the Minimum:

The first element visited by inorder traversal is the minimum value in the BST
This node is found by following left pointers from the root until we reach a node with no left child
Why? Because inorder traversal exhausts all left subtrees before visiting any node

Finding the Maximum:

The last element visited by inorder traversal is the maximum value in the BST
This node is found by following right pointers from the root until we reach a node with no right child
Why? Because inorder traversal visits all right subtrees after visiting each node

find_min_max.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def find_minimum(node):
    """
    Find the minimum value in a BST.
    
    The minimum is the leftmost node in the tree - the same node
    that inorder traversal would visit first.
    
    Time Complexity: O(h) where h is the height of the tree
    Space Complexity: O(1)
    """
    if node is None:
        return None
    
    current = node
    # Keep going left until we can't go anymore
    while current.left is not None:
        current = current.left
    
    return current.value
 
 
def find_maximum(node):
    """
    Find the maximum value in a BST.
    
    The maximum is the rightmost node in the tree - the same node
    that inorder traversal would visit last.
    
    Time Complexity: O(h) where h is the height of the tree
    Space Complexity: O(1)
    """
    if node is None:
        return None
    
    current = node
    # Keep going right until we can't go anymore
    while current.right is not None:
        current = current.right
    
    return current.value
 
 
# These operations directly leverage the sorted output property!
# Minimum = first in sorted order = leftmost node
# Maximum = last in sorted order = rightmost node

The connection to sorted arrays:

This is analogous to a sorted array where:

array[0] is the minimum (first element)
array[n-1] is the maximum (last element)

The BST provides similar "sorted" access, but with the added ability to efficiently insert and delete elements while maintaining order—something sorted arrays struggle with.

Inorder Successor and Predecessor

The sorted output property gives meaning to two critical concepts:

Finding Inorder Successor

•Case 1: Node has a right subtree → The successor is the minimum node in the right subtree (leftmost node in right subtree)
•Case 2: Node has no right subtree → The successor is the lowest ancestor for which this node is in the left subtree (walk up until we came from the left)

Finding Inorder Predecessor

•Case 1: Node has a left subtree → The predecessor is the maximum node in the left subtree (rightmost node in left subtree)
•Case 2: Node has no left subtree → The predecessor is the lowest ancestor for which this node is in the right subtree (walk up until we came from the right)

Why This Matters for Deletion

The Elegance of This Property

Step back and appreciate what we've discovered:

A BST is a sorted collection in disguise.

This dual nature—a tree structure that encodes a sorted sequence—is what makes BSTs so versatile:

BST: Combining Tree and Sorted Sequence Benefits
Capability	How BST Provides It	Complexity
Find minimum	Go leftmost	O(h)
Find maximum	Go rightmost	O(h)
Find any element	Binary search traversal	O(h)
Insert while maintaining order	Find position, attach	O(h)
Delete while maintaining order	Use successor/predecessor	O(h)
Get all elements in sorted order	Inorder traversal	O(n)
Find k-th smallest element	Inorder traversal to k	O(k + h)
Find elements in range	Modified inorder	O(h + k)

The trade-off with arrays:

Compare this to a sorted array:

Arrays give O(1) access to any position but O(n) insertion/deletion
BSTs give O(h) access to any element with O(h) insertion/deletion

Summary: The Sorted Output Property

We've established one of the most fundamental properties of Binary Search Trees. Let's consolidate what we've learned:

Key Takeaways

•Inorder traversal (L-N-R) of a BST produces elements in ascending sorted order — This is an inevitable consequence of the BST property, not a coincidence.
•The BST property ensures left < node < right for ALL descendants — This recursive constraint is what guarantees sorted output, not just immediate children.
•Minimum is the leftmost node; maximum is the rightmost — The first and last elements in sorted order are found by following left/right pointers to their ends.
•Inorder successor/predecessor define 'next' and 'previous' in sorted order — These concepts are crucial for BST deletion and range operations.
•A BST is a dynamic sorted collection — It maintains sorted order through structure, enabling efficient insertion and deletion unlike static sorted arrays.
•Understanding this property is foundational — Almost every BST algorithm leverages the sorted output property in some way.

What's next:

Page Complete

1 / 4