Solving Convert Sorted Array to BST in Go: Step-by-Step Guide

Introduction to Convert Sorted Array to BST

The "Convert Sorted Array to Binary Search Tree" problem is a classic algorithmic challenge frequently encountered in coding interviews and competitive programming. Given an integer array sorted in ascending order, the task is to construct a height-balanced binary search tree (BST). A height-balanced BST is one where the depth of the two subtrees of every node never differs by more than one.

This problem elegantly combines two fundamental computer science concepts: binary search and tree construction. Because the input array is already sorted, we can leverage the properties of binary search to pick the middle element as the root, ensuring the left and right subtrees contain roughly equal numbers of nodes. This guarantees the resulting tree is height-balanced.

Why It Matters

Understanding how to convert a sorted array into a BST is important for several reasons. First, it demonstrates mastery of recursion and divide-and-conquer strategies, which are essential techniques for solving complex problems efficiently. Second, balanced BSTs provide O(log n) time complexity for search, insertion, and deletion operations, making them valuable data structures for databases, file systems, and indexing mechanisms.

In real-world applications, you might encounter this scenario when migrating sorted data from a flat storage format into a tree-based index, or when building balanced search structures from pre-sorted datasets. Mastering this problem also builds intuition for related challenges, such as converting sorted linked lists to BSTs or balancing existing binary trees.

Understanding the Approach

The Core Idea

The key insight is that the middle element of a sorted array naturally becomes the root of a balanced BST. All elements to the left of the middle are smaller and belong in the left subtree, while all elements to the right are larger and belong in the right subtree. We apply this logic recursively to build the entire tree.

Step-by-Step Algorithm

Identify the middle index of the current subarray.
Create a tree node using the middle element as its value.
Recursively build the left subtree using the left half of the array.
Recursively build the right subtree using the right half of the array.
Return the constructed node as the root of this subtree.
Base case: when the start index exceeds the end index, return nil.

Implementing the Solution in Go

Defining the Tree Node

First, we need to define the structure for a binary tree node. In Go, we use a struct with a value and pointers to left and right children.

package main

import "fmt"

// TreeNode represents a node in the binary search tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

The Recursive Function

Next, we implement the core recursive function that builds the BST from a subarray defined by start and end indices. Using indices rather than slicing the array avoids unnecessary memory allocations and keeps the time complexity at O(n).

// sortedArrayToBST converts a sorted array into a height-balanced BST.
func sortedArrayToBST(nums []int) *TreeNode {
    return buildBST(nums, 0, len(nums)-1)
}

// buildBST recursively constructs a BST from the subarray nums[left..right].
func buildBST(nums []int, left, right int) *TreeNode {
    // Base case: no elements to process
    if left > right {
        return nil
    }

    // Find the middle index. Using left + (right-left)/2 avoids
    // potential integer overflow compared to (left+right)/2.
    mid := left + (right-left)/2

    // Create the root node with the middle element
    root := &TreeNode{Val: nums[mid]}

    // Recursively build left and right subtrees
    root.Left = buildBST(nums, left, mid-1)
    root.Right = buildBST(nums, mid+1, right)

    return root
}

Helper Function to Verify the Tree

To confirm our solution works correctly, let us write a helper function that performs an in-order traversal. For a valid BST built from a sorted array, the in-order traversal should reproduce the original sorted array.

// inOrderTraversal prints the tree using in-order traversal.
func inOrderTraversal(root *TreeNode) []int {
    result := []int{}
    var traverse func(node *TreeNode)
    traverse = func(node *TreeNode) {
        if node == nil {
            return
        }
        traverse(node.Left)
        result = append(result, node.Val)
        traverse(node.Right)
    }
    traverse(root)
    return result
}

// treeHeight calculates the height of the tree.
func treeHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := treeHeight(root.Left)
    rightHeight := treeHeight(root.Right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

// isBalanced checks whether the tree is height-balanced.
func isBalanced(root *TreeNode) bool {
    var check func(node *TreeNode) (int, bool)
    check = func(node *TreeNode) (int, bool) {
        if node == nil {
            return 0, true
        }
        leftHeight, leftBalanced := check(node.Left)
        rightHeight, rightBalanced := check(node.Right)
        balanced := leftBalanced && rightBalanced
        diff := leftHeight - rightHeight
        if diff < 0 {
            diff = -diff
        }
        if diff > 1 {
            balanced = false
        }
        height := leftHeight
        if rightHeight > height {
            height = rightHeight
        }
        return height + 1, balanced
    }
    _, balanced := check(root)
    return balanced
}

Putting It All Together

Now let us write the main function to test our implementation with a sample sorted array.

func main() {
    nums := []int{-10, -3, 0, 5, 9}

    root := sortedArrayToBST(nums)

    // Verify in-order traversal reproduces the sorted array
    traversal := inOrderTraversal(root)
    fmt.Println("In-order traversal:", traversal)
    // Output: In-order traversal: [-10 -3 0 5 9]

    // Verify the tree is height-balanced
    fmt.Println("Is balanced:", isBalanced(root))
    // Output: Is balanced: true

    // Print the tree height
    fmt.Println("Tree height:", treeHeight(root))
    // Output: Tree height: 3

    // Test with an empty array
    emptyRoot := sortedArrayToBST([]int{})
    fmt.Println("Empty tree root:", emptyRoot)
    // Output: Empty tree root: <nil>

    // Test with a single element
    singleRoot := sortedArrayToBST([]int{42})
    fmt.Println("Single element in-order:", inOrderTraversal(singleRoot))
    // Output: Single element in-order: [42]
}

Complexity Analysis

Understanding the time and space complexity of this solution is crucial for evaluating its efficiency.

Time Complexity: O(n), where n is the number of elements in the array. Each element is visited exactly once to create a tree node.
Space Complexity: O(log n) for the recursion stack in the average case, since the tree is height-balanced. In the worst case of a degenerate system with limited stack, this could be O(n). Additionally, O(n) space is used to store the tree nodes themselves.

Best Practices

Use Index-Based Recursion

Avoid slicing the array at each recursive step. While nums[mid+1:] might look cleaner, it creates new slices and adds overhead. Passing indices keeps memory usage minimal and improves performance, especially for large arrays.

Prevent Integer Overflow

When calculating the middle index, use left + (right-left)/2 instead of (left+right)/2. Although Go handles integer overflow differently than some languages, this habit is a good defensive programming practice that translates well across languages.

Handle Edge Cases

Always consider edge cases such as empty arrays, single-element arrays, and arrays with duplicate values. The base case left > right naturally handles empty and single-element scenarios, but you should test these explicitly.

Verify with Traversals

After constructing the tree, verify correctness using in-order traversal, which should reproduce the original sorted array. Additionally, check that the tree is height-balanced using a dedicated balance-checking function.

Consider Iterative Alternatives

For extremely large arrays where recursion depth might be a concern, consider an iterative approach using an explicit stack. While the recursive solution is more readable and idiomatic in Go, the iterative version eliminates recursion depth limitations entirely.

// sortedArrayToBSTIterative builds a BST iteratively using a stack.
func sortedArrayToBSTIterative(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }

    type frame struct {
        node   *TreeNode
        left   int
        right  int
        isLeft bool
    }

    mid := (len(nums) - 1) / 2
    root := &TreeNode{Val: nums[mid]}
    stack := []frame{
        {node: root, left: 0, right: mid - 1, isLeft: true},
        {node: root, left: mid + 1, right: len(nums) - 1, isLeft: false},
    }

    for len(stack) > 0 {
        f := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if f.left > f.right {
            continue
        }

        m := f.left + (f.right-f.left)/2
        child := &TreeNode{Val: nums[m]}

        if f.isLeft {
            f.node.Left = child
        } else {
            f.node.Right = child
        }

        stack = append(stack, frame{node: child, left: f.left, right: m - 1, isLeft: true})
        stack = append(stack, frame{node: child, left: m + 1, right: f.right, isLeft: false})
    }

    return root
}

Common Pitfalls to Avoid

Off-by-one errors: Ensure the base case uses left > right and recursive calls use mid-1 and mid+1 to exclude the middle element.
Forgetting nil checks: Always handle the empty array case to avoid panics when accessing nums[mid].
Confusing BST with binary tree: Remember that a BST requires left children to be smaller and right children to be larger than the parent. The sorted array property guarantees this when the middle element is chosen as root.
Ignoring balance verification: Just because the algorithm should produce a balanced tree does not mean you should skip testing for balance, especially when modifying the algorithm.

Conclusion

Converting a sorted array into a height-balanced binary search tree is a foundational problem that reinforces essential concepts in recursion, divide-and-conquer, and tree data structures. By selecting the middle element as the root at each step and recursively processing the left and right halves, we achieve an elegant O(n) solution that produces a balanced tree. The Go implementation demonstrates how clean and readable this algorithm can be, while best practices such as index-based recursion, overflow-safe midpoint calculation, and thorough edge-case testing ensure the solution is both efficient and robust. Whether you are preparing for coding interviews or building real-world indexing systems, mastering this technique provides a solid foundation for tackling more advanced tree manipulation problems.