Convert BST to Sorted Array — In-Order Traversal

Sorted data is the foundation of fast searching, clean output, and reliable comparisons. But in the real world, data rarely arrives pre-sorted in an array — it's often stored in a BST because insertion and lookup are O(log n). When you need to export that data, merge it with another dataset, or display it to a user, you need a flat, sorted list. Knowing how to flatten a BST into a sorted array efficiently is a skill that shows up everywhere from database query engines to autocomplete systems.

The problem this solves is deceptively simple to state but easy to get wrong: given the root of a BST, produce an array where every element is in ascending order. The naive approach — dump all nodes into an array and call Arrays.sort() — works but wastes the BST's built-in ordering guarantee entirely. The smart approach exploits the BST property directly, giving you a sorted array in O(n) time with zero comparisons.

By the end of this article you'll understand exactly why in-order traversal produces sorted output (not just that it does), you'll have two complete runnable implementations (recursive and iterative), you'll know the three most common mistakes developers make, and you'll be ready to field the interview questions that trip people up most.

What is Convert BST to Sorted Array? — Plain English

A Binary Search Tree (BST) has a fundamental property: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. In-order traversal (left → root → right) of a BST visits nodes in ascending sorted order. This means converting a BST to a sorted array is as simple as performing an in-order traversal and collecting node values. The reverse direction — converting a sorted array to a height-balanced BST — works by always picking the middle element of the current subarray as the root, then recursively building the left subtree from the left half and right subtree from the right half. This ensures the tree is balanced because both halves have roughly equal size.

How the Conversion Works — Step by Step

BST to sorted array via in-order traversal: 1. If current node is None, return. 2. Recursively traverse left subtree. 3. Append current node's value to result. 4. Recursively traverse right subtree. 5. The result list is sorted because BST property guarantees left < root < right.

Sorted array to balanced BST: 1. If array is empty, return None. 2. Find mid = len(array) // 2. 3. Create a TreeNode with value array[mid]. 4. node.left = recursively build from array[:mid]. 5. node.right = recursively build from array[mid+1:]. 6. Return node.

For array [1,2,3,4,5,6,7]: mid=3 (value 4) becomes root. Left subtree from [1,2,3]: mid=1 (value 2). Right subtree from [5,6,7]: mid=1 (value 6). This produces a perfectly balanced BST of height 2.

Worked Example — Tracing Both Directions

BST: 4 / \ 2 6 / \ / \ 1 3 5 7

In-order traversal → sorted array: 1. Go left from 4 to 2. Go left from 2 to 1. 1 has no children → append 1. 2. Back to 2 → append 2. Go right to 3 → append 3. 3. Back to 4 → append 4. Go right to 6. 4. Go left from 6 to 5 → append 5. Back to 6 → append 6. Right to 7 → append 7. 5. Result: [1,2,3,4,5,6,7].

Now reverse: sorted [1,2,3,4,5,6,7] → BST: - mid=3 → root=4. Left from [1,2,3]: mid=1 → root=2, left=1, right=3. - Right from [5,6,7]: mid=1 → root=6, left=5, right=7. - Tree is exactly the original BST above. Height = 2, perfectly balanced.

Implementation

Both directions are clean recursive implementations. BST to array uses in-order DFS. Array to BST uses divide-and-conquer, always picking the midpoint as root. The BST-to-array runs in O(n) time and O(n) space (result + call stack). The array-to-BST also runs in O(n) time and O(log n) stack space for a balanced input. An iterative in-order traversal using an explicit stack avoids recursion depth issues for very deep trees.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val; self.left = left; self.right = right

def bst_to_sorted_array(root):
    """In-order traversal → sorted list."""
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

def sorted_array_to_bst(nums):
    """Sorted array → height-balanced BST."""
    if not nums:
        return None
    mid = len(nums) // 2
    node = TreeNode(nums[mid])
    node.left = sorted_array_to_bst(nums[:mid])
    node.right = sorted_array_to_bst(nums[mid+1:])
    return node

# Build BST manually and convert
root = TreeNode(4)
root.left = TreeNode(2, TreeNode(1), TreeNode(3))
root.right = TreeNode(6, TreeNode(5), TreeNode(7))

arr = bst_to_sorted_array(root)
print(arr)  # [1, 2, 3, 4, 5, 6, 7]

# Rebuild BST from sorted array
new_root = sorted_array_to_bst(arr)
print(bst_to_sorted_array(new_root))  # [1, 2, 3, 4, 5, 6, 7]

Frequently Asked Questions