Convert BST to Sorted Array Using In-Order Traversal (Java)
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.
Why In-Order Traversal Naturally Produces Sorted Output
The BST property guarantees a strict ordering contract: for any node N, every value in N's left subtree is less than N's value, and every value in N's right subtree is greater. This isn't just a convention — it's a structural invariant enforced on every insertion.
In-order traversal visits nodes in the sequence: left subtree → current node → right subtree. Apply the BST property recursively and you can prove this always yields ascending order. When you visit the left subtree first, you collect everything smaller than the current node. Then you record the current node. Then you visit the right subtree, collecting everything larger. At every level of the tree, this contract holds — so the final collected sequence is globally sorted.
This is fundamentally different from pre-order or post-order traversal. Pre-order visits the root before its children, which gives you insertion order, not sorted order. Post-order visits children before the root, useful for deletion but not sorting. Only in-order maps cleanly onto the BST's sorted structure.
The payoff: you get a sorted array in O(n) time and O(n) space (for the output array), with O(h) additional space for the call stack where h is the tree height. No comparisons, no swaps. The BST already did all the sorting work during insertion.
import java.util.ArrayList; import java.util.List; public class BstToSortedArrayRecursive { // A single node in the BST static class TreeNode { int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; } } /** * Inserts a value into the BST, maintaining the BST ordering property. * Values less than the current node go left; greater go right. */ static TreeNode insert(TreeNode root, int value) { if (root == null) { return new TreeNode(value); // Base case: empty spot found, place the node here } if (value < root.value) { root.left = insert(root.left, value); // Smaller values belong in the left subtree } else { root.right = insert(root.right, value); // Larger values belong in the right subtree } return root; } /** * In-order traversal: LEFT → CURRENT → RIGHT * Because of the BST property, this visits nodes in ascending order. * We collect each visited value directly into the result list. */ static void inOrderCollect(TreeNode node, List<Integer> sortedValues) { if (node == null) { return; // Nothing to visit — base case for the recursion } inOrderCollect(node.left, sortedValues); // Step 1: Recurse into the left (smaller) subtree sortedValues.add(node.value); // Step 2: Record this node AFTER all smaller nodes inOrderCollect(node.right, sortedValues); // Step 3: Recurse into the right (larger) subtree } /** * Public-facing method: builds the BST and converts it to a sorted int array. */ static int[] convertBstToSortedArray(int[] inputValues) { TreeNode root = null; // Build the BST by inserting each value one at a time for (int value : inputValues) { root = insert(root, value); } // Collect all values via in-order traversal into a list List<Integer> sortedValues = new ArrayList<>(); inOrderCollect(root, sortedValues); // Convert the List<Integer> to a primitive int[] for practical use int[] sortedArray = new int[sortedValues.size()]; for (int i = 0; i < sortedValues.size(); i++) { sortedArray[i] = sortedValues.get(i); } return sortedArray; } public static void main(String[] args) { int[] unsortedInput = {50, 30, 70, 20, 40, 60, 80}; System.out.println("Input (insertion order): "); for (int value : unsortedInput) { System.out.print(value + " "); } System.out.println(); int[] sortedResult = convertBstToSortedArray(unsortedInput); System.out.println("Output (sorted array): "); for (int value : sortedResult) { System.out.print(value + " "); } System.out.println(); } }
50 30 70 20 40 60 80
Output (sorted array):
20 30 40 50 60 70 80
Iterative In-Order Traversal — When the Call Stack Isn't Your Friend
The recursive solution is elegant, but it has a real-world weakness: stack overflow. In Java, each recursive call consumes a stack frame. For a balanced BST with one million nodes, the height is about 20 levels — totally fine. But a BST built from already-sorted input (like inserting 1, 2, 3, 4, 5 in order) degenerates into a linked list with height n. One million nodes means one million stack frames — that's a StackOverflowError in production.
The iterative approach simulates the call stack explicitly using a Deque (or Stack). The logic mirrors the recursive version exactly: go as far left as possible, process the current node, then shift to the right subtree. You're in complete control of memory, and you can handle arbitrarily deep trees without crashing.
This pattern — replacing recursion with an explicit stack — is a critical technique to know. It appears in tree serialization, expression parsers, and file system walkers. Interviewers love asking for the iterative version after you give the recursive one, precisely because it tests whether you understand what recursion is actually doing under the hood.
In practice, always reach for the iterative solution when you can't guarantee tree balance in production code.
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.List; public class BstToSortedArrayIterative { static class TreeNode { int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; } } static TreeNode insert(TreeNode root, int value) { if (root == null) return new TreeNode(value); if (value < root.value) root.left = insert(root.left, value); else root.right = insert(root.right, value); return root; } /** * Iterative in-order traversal using an explicit stack. * This avoids StackOverflowError on degenerate (unbalanced) trees. * * The loop runs until both conditions are true: * - currentNode is null (no more nodes to dive into) * - the stack is empty (no pending nodes to backtrack to) */ static int[] convertBstToSortedArrayIterative(TreeNode root) { List<Integer> sortedValues = new ArrayList<>(); Deque<TreeNode> pendingNodes = new ArrayDeque<>(); // Acts as our manual call stack TreeNode currentNode = root; while (currentNode != null || !pendingNodes.isEmpty()) { // Phase 1: Dive as far LEFT as possible, pushing each node onto the stack // This mirrors the recursive call inOrderCollect(node.left, ...) while (currentNode != null) { pendingNodes.push(currentNode); // Save this node; we'll process it after its left subtree currentNode = currentNode.left; // Keep going left } // Phase 2: We've hit a null left child — backtrack to the last saved node currentNode = pendingNodes.pop(); // This is the leftmost unprocessed node sortedValues.add(currentNode.value); // PROCESS: record it (mirrors sortedValues.add in recursion) // Phase 3: Now explore the RIGHT subtree of the node we just processed // The outer while loop will then dive left again from here currentNode = currentNode.right; } // Convert List<Integer> to int[] return sortedValues.stream().mapToInt(Integer::intValue).toArray(); } public static void main(String[] args) { // Test 1: Normal BST int[] normalInput = {50, 30, 70, 20, 40, 60, 80}; TreeNode balancedRoot = null; for (int value : normalInput) { balancedRoot = insert(balancedRoot, value); } System.out.println("Balanced BST sorted: " + Arrays.toString(convertBstToSortedArrayIterative(balancedRoot))); // Test 2: Degenerate BST (sorted insertion = linked list shape) // This would cause StackOverflowError with deep recursion int[] sortedInput = {10, 20, 30, 40, 50, 60, 70}; // Each insert goes right only TreeNode degenerateRoot = null; for (int value : sortedInput) { degenerateRoot = insert(degenerateRoot, value); } System.out.println("Degenerate BST sorted: " + Arrays.toString(convertBstToSortedArrayIterative(degenerateRoot))); // Test 3: Single node TreeNode singleNode = new TreeNode(42); System.out.println("Single node sorted: " + Arrays.toString(convertBstToSortedArrayIterative(singleNode))); // Test 4: Null root (empty tree) System.out.println("Empty tree sorted: " + Arrays.toString(convertBstToSortedArrayIterative(null))); } }
Degenerate BST sorted: [10, 20, 30, 40, 50, 60, 70]
Single node sorted: [42]
Empty tree sorted: []
Real-World Patterns — When and Why You'd Actually Do This
Knowing the algorithm is one thing. Knowing when to reach for it in real code is what separates good engineers from great ones. Here are three concrete scenarios where BST-to-sorted-array conversion earns its keep.
First: reporting and export. An application might maintain a BST of event timestamps during runtime for fast O(log n) insertions. When a user exports a report, you flatten it once into a sorted array, serialize to CSV, and discard the tree. One-time linear cost, clean output.
Second: merging sorted datasets. If you have two BSTs and need one merged sorted array, you flatten both into sorted arrays in O(n) and O(m) time, then use the classic two-pointer merge in O(n+m). This is often faster than re-inserting all nodes into a new BST and traversing it.
Third: kth smallest/largest element. Flattening to a sorted array lets you answer 'find the kth smallest element' in O(1) after the O(n) flatten. For repeated kth-element queries on a static tree, this amortizes beautifully. For a dynamic tree with frequent insertions, you'd want an augmented BST instead.
The comparison table below helps you pick the right tool for the job between the recursive and iterative approaches.
import java.util.Arrays; public class MergeTwoBsts { static class TreeNode { int value; TreeNode left, right; TreeNode(int value) { this.value = value; } } static TreeNode insert(TreeNode root, int value) { if (root == null) return new TreeNode(value); if (value < root.value) root.left = insert(root.left, value); else root.right = insert(root.right, value); return root; } // Flatten a BST into a sorted array using recursive in-order traversal static void inOrderCollect(TreeNode node, int[] buffer, int[] indexTracker) { if (node == null) return; inOrderCollect(node.left, buffer, indexTracker); buffer[indexTracker[0]++] = node.value; // indexTracker[0] acts as a mutable index counter inOrderCollect(node.right, buffer, indexTracker); } static int countNodes(TreeNode node) { if (node == null) return 0; return 1 + countNodes(node.left) + countNodes(node.right); } /** * Merges two BSTs into a single sorted array. * Strategy: flatten each BST independently, then merge the two sorted arrays * using the classic two-pointer technique — O(n + m) time. */ static int[] mergeTwoBsts(TreeNode rootA, TreeNode rootB) { int sizeA = countNodes(rootA); int sizeB = countNodes(rootB); // Flatten each BST into its own sorted array int[] sortedA = new int[sizeA]; int[] sortedB = new int[sizeB]; inOrderCollect(rootA, sortedA, new int[]{0}); // new int[]{0} is a mutable index wrapper inOrderCollect(rootB, sortedB, new int[]{0}); // Two-pointer merge of two sorted arrays int[] mergedResult = new int[sizeA + sizeB]; int pointerA = 0, pointerB = 0, mergeIndex = 0; while (pointerA < sizeA && pointerB < sizeB) { if (sortedA[pointerA] <= sortedB[pointerB]) { mergedResult[mergeIndex++] = sortedA[pointerA++]; // A's current element is smaller } else { mergedResult[mergeIndex++] = sortedB[pointerB++]; // B's current element is smaller } } // Drain any remaining elements from either array while (pointerA < sizeA) mergedResult[mergeIndex++] = sortedA[pointerA++]; while (pointerB < sizeB) mergedResult[mergeIndex++] = sortedB[pointerB++]; return mergedResult; } public static void main(String[] args) { // BST A: contains employee IDs from Department 1 TreeNode deptOneBst = null; for (int id : new int[]{40, 20, 60, 10, 30}) { deptOneBst = insert(deptOneBst, id); } // BST B: contains employee IDs from Department 2 TreeNode deptTwoBst = null; for (int id : new int[]{50, 25, 75, 5, 55}) { deptTwoBst = insert(deptTwoBst, id); } int[] allEmployeeIds = mergeTwoBsts(deptOneBst, deptTwoBst); System.out.println("All employee IDs (merged, sorted): " + Arrays.toString(allEmployeeIds)); } }
| Aspect | Recursive In-Order | Iterative In-Order |
|---|---|---|
| Code readability | Very clean — mirrors the definition directly | More verbose — explicit stack management |
| Risk of StackOverflow | Yes — on degenerate trees (height = n) | No — uses heap-allocated Deque instead |
| Space complexity (extra) | O(h) implicit call stack; O(n) worst case | O(h) explicit Deque; O(n) worst case |
| Time complexity | O(n) — visits each node once | O(n) — visits each node once |
| Best for | Balanced trees, interviews, prototyping | Production code, unknown input distributions |
| Debuggability | Harder — stack frames aren't directly inspectable | Easier — you can inspect the Deque at any point |
| Tail-call optimization | Java does NOT optimize tail calls — no benefit here | N/A — no recursion to optimize |
🎯 Key Takeaways
- In-order traversal (left → current → right) produces sorted output on a BST because it directly reads the BST ordering invariant — no comparisons needed, giving you O(n) instead of O(n log n).
- The recursive solution is elegant but dangerous on degenerate trees — any sorted or nearly-sorted insertion order produces a tree with height n, which translates to n stack frames and a potential StackOverflowError in Java.
- The iterative solution using an explicit Deque is the production-safe choice — it has identical time and space complexity but uses heap memory for the stack, which is far larger and controllable.
- Flattening a BST to a sorted array is a composable primitive — it unlocks fast range queries via binary search, enables O(n+m) two-BST merges via two-pointer merge, and makes kth-element lookups O(1) after a one-time O(n) cost.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Building the BST from already-sorted input and expecting it to be balanced — The tree degenerates into a right-skewed linked list (height = n), making traversal O(n) stack depth and causing StackOverflowError on large inputs — Fix: shuffle input before building, use an iterative traversal, or use a self-balancing structure like Java's TreeMap.
- ✕Mistake 2: Using a List
index manually inside the recursive method without a mutable wrapper — You try to pass an int index into the recursive helper, increment it, and find the outer method still sees index = 0 because primitives are passed by value in Java — Fix: wrap the index in an int[] of size 1 (e.g., int[] idx = {0}) or use a class-level field, so the recursive calls share the same mutable reference. - ✕Mistake 3: Forgetting to handle duplicate values consistently — If you insert duplicates (e.g., 30, 30) without a clear rule (always left, always right, or discard), your BST property becomes ambiguous and the sorted output may have unexpected ordering — Fix: decide on a deduplication or placement strategy at insertion time: use value < root.value for strict left placement of duplicates, or add a count field to each node and skip duplicate nodes in the output.
Interview Questions on This Topic
- QGiven the root of a BST, write a method that returns all elements as a sorted array. Now rewrite it without recursion. What changes and why?
- QWhat is the time and space complexity of converting a BST to a sorted array, and how does tree balance affect both in practice?
- QIf I insert the values 1 through 1,000,000 in sorted order into a BST and then call your recursive in-order traversal, what happens and how do you fix it?
Frequently Asked Questions
Why does in-order traversal of a BST give a sorted array?
The BST property guarantees that every node in a left subtree is smaller than the current node, and every node in a right subtree is larger. In-order traversal visits the left subtree first, then the current node, then the right subtree — which maps perfectly onto ascending order. At every level of the tree this contract holds, so the globally collected sequence is always sorted.
What is the time complexity of converting a BST to a sorted array?
It's O(n) where n is the number of nodes. You visit each node exactly once and do O(1) work per node (adding to a list). Space complexity is O(n) for the output array plus O(h) for the traversal stack, where h is the tree height — O(log n) for a balanced tree and O(n) in the worst case for a degenerate one.
Can I convert a BST to a sorted array without using extra space for the array?
If you must produce a sorted array, the O(n) output space is unavoidable — the array itself requires n slots. You can reduce auxiliary space (beyond the output) to O(1) using Morris Traversal, which threads temporary pointers through the tree to navigate without a stack. However, Morris Traversal temporarily modifies the tree structure, so it's only safe if you own the tree and can restore it afterwards.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.