BST to Sorted Array — Degenerate Tree Stack Overflow Fix

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]

Production Considerations: Recursion Limits and Iterative Alternatives

Recursive in-order traversal is clean but dangerous in production. A degenerate BST (height = n) consumes O(n) call stack space. In Java, default stack size is often 1MB, which may overflow near 10,000–20,000 recursive calls depending on frame size. Iterative traversal using an explicit stack (Deque) offers predictable memory usage and avoids stack overflow regardless of tree shape. The iterative algorithm uses a while loop and a stack to simulate recursion: push left until null, pop, process, move right.

Java implementation: ``java public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; } `` This runs in O(n) time and O(h) extra space (stack). For production systems handling untrusted or unbalanced trees, prefer iterative traversal. For balanced trees, recursion is acceptable if stack monitors are in place.

Performance insight: Recursive traversal on a balanced tree of 1 million nodes uses ~log2(n) ≈ 20 stack frames, negligible. On a degenerate tree, it uses 1 million frames, likely crashing.

package io.thecodeforge;

import java.util.*;

public class InorderIterative {
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        return result;
    }
}

Edge Cases: Duplicates, Null Input, and BST Validation

BST to sorted array conversion assumes a valid BST. Edge cases include: - Null root: return empty list. - Duplicate values: BST property typically enforces strict left < root < right. If duplicates are allowed (non-strict), the sorted array may contain consecutive equal values. Ensure insertion policy is consistent. - Single node: return [value]. - Tree with only left children: degenerate left-skewed – works fine but recursion depth may be high. - Tree with only right children: same.

Validation: Before trusting traversal output, validate the BST with in-order check or recursive bounds. A common bug is assuming the tree is a valid BST when it isn't.

Performance insight: Validating BST via in-order takes O(n) time and O(h) space, same as conversion.

def is_valid_bst(root):
    prev = None
    stack = []
    curr = root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        if prev is not None and curr.val <= prev:
            return False
        prev = curr.val
        curr = curr.right
    return True

Why Picking the Middle Element is a Tree-Balancing Hack, Not a Law

Every tutorial tells you to pick the middle element. They call it "ensuring balance." That's half the truth. The real reason: picking the median guarantees that the left and right subtrees differ by at most one node. It's a greedy divide-and-conquer that maps perfectly to the array's sorted nature.

But here's the production trap: this only works if your array is perfectly sorted. Throw a rotation flag or a timestamp-based insert order at this, and your "balanced" tree degrades into a linked list faster than a junior's first microservice. The middle-element hack assumes your input is already homogenous and sorted. If it isn't, you need AVL or Red-Black self-balancing logic.

For the standard problem, yes — take the middle index, recurse left and right. It's O(n) time and O(n) space because you're building a new tree, not modifying in-place. The call stack depth is O(log n) for a balanced tree, but if the recursion hits 10,000 nodes, you'll blow the stack on any JVM without tuning. That's the hidden cost nobody mentions.

// io.thecodeforge — dsa tutorial

public class SortedArrayToBalancedBST {
    public TreeNode sortedArrayToBST(int[] sorted) {
        if (sorted == null || sorted.length == 0) return null;
        return build(sorted, 0, sorted.length - 1);
    }

    private TreeNode build(int[] sorted, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(sorted[mid]);
        node.left = build(sorted, left, mid - 1);
        node.right = build(sorted, mid + 1, right);
        return node;
    }

    public static void main(String[] args) {
        SortedArrayToBalancedBST converter = new SortedArrayToBalancedBST();
        int[] array = {1, 5, 9, 14, 23, 27};
        TreeNode root = converter.sortedArrayToBST(array);
        // Level-order: [9, 1, 23, null, 5, 14, 27]
        System.out.println(root.val); // 9
    }
}

Iterative Construction via Queue: When Recursion Fails in Production

Recursion is elegant until your heap dump shows 1000+ stack frames. Then it's a liability. The iterative approach using a BFS-style queue builds the tree in breadth-first order, avoiding recursion depth issues entirely.

How it works: You start with a queue of range tuples — each tuple holds a parent node and the left/right indices of the subarray. Pop one range, compute the middle index, create a child node, and attach it to the parent. If the parent already has a left child, attach to the right; otherwise, attach to the left. Push the child's subarray ranges back into the queue.

This runs O(n) time and O(n) space — same Big-O as recursion — but the space is heap-allocated, not stack-allocated. That's critical when your tree holds millions of nodes. The queue depth never exceeds the number of incomplete nodes, which for a balanced tree is O(n) in the worst case.

The trade-off: more code complexity. You're managing state explicitly. But when your CI pipeline starts throwing StackOverflowErrors on deep trees, this refactor pays for itself in the first incident post-mortem.

// io.thecodeforge — dsa tutorial

import java.util.ArrayDeque;
import java.util.Deque;

public class IterativeBalancedBST {
    public TreeNode sortedArrayToBST(int[] sorted) {
        if (sorted == null || sorted.length == 0) return null;
        TreeNode root = new TreeNode(0);
        Deque<int[]> rangeQueue = new ArrayDeque<>();
        Deque<TreeNode> nodeQueue = new ArrayDeque<>();
        rangeQueue.offer(new int[]{0, sorted.length - 1});
        nodeQueue.offer(root);

        while (!rangeQueue.isEmpty()) {
            int[] range = rangeQueue.poll();
            TreeNode parent = nodeQueue.poll();
            int mid = range[0] + (range[1] - range[0]) / 2;
            parent.val = sorted[mid];

            if (mid > range[0]) {
                parent.left = new TreeNode(0);
                rangeQueue.offer(new int[]{range[0], mid - 1});
                nodeQueue.offer(parent.left);
            }
            if (mid < range[1]) {
                parent.right = new TreeNode(0);
                rangeQueue.offer(new int[]{mid + 1, range[1]});
                nodeQueue.offer(parent.right);
            }
        }
        return root;
    }
}