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