Convert Sorted Array to Balanced BST in DSA Go

Mental Model

We pick the middle element of the sorted array as the root to keep the tree balanced. Then we do the same for left and right parts to build left and right subtrees.

Analogy: Imagine you have a sorted list of books on a shelf. To build a balanced stack, you pick the middle book first as the base, then stack books from the left and right halves evenly on each side.

Sorted array: [1, 2, 3, 4, 5, 6, 7]
Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Dry Run Walkthrough

Input: sorted array: [1, 2, 3, 4, 5, 6, 7]

Goal: Build a balanced binary search tree from the sorted array

Step 1: Pick middle element 4 as root

Tree: 4
Array split: left=[1,2,3], right=[5,6,7]

Why: Middle element keeps tree balanced by dividing array evenly

Step 2: Build left subtree from [1,2,3], pick middle 2 as left child

Tree:
    4
   /
  2
Array split left=[1], right=[3]

Why: Recursively pick middle to keep left subtree balanced

Step 3: Build left child of 2 from [1], pick 1

Tree:
    4
   /
  2
 /
1

Why: Single element becomes leaf node

Step 4: Build right child of 2 from [3], pick 3

Tree:
    4
   /
  2
 / \
1   3

Why: Single element becomes leaf node

Step 5: Build right subtree from [5,6,7], pick middle 6 as right child

Tree:
    4
   / \
  2   6
 / \

Why: Recursively pick middle to keep right subtree balanced

Step 6: Build left child of 6 from [5], pick 5

Tree:
    4
   / \
  2   6
 / \ /
1  3 5

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], pick 7

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

Why: Single element becomes leaf node

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

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

// sortedArrayToBST converts a sorted array to a balanced BST
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    mid := len(nums) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = sortedArrayToBST(nums[:mid])
    root.Right = sortedArrayToBST(nums[mid+1:])
    return root
}

// printBST prints the BST in order with arrows
func printBST(root *TreeNode) {
    if root == nil {
        return
    }
    printBST(root.Left)
    fmt.Printf("%d ", root.Val)
    printBST(root.Right)
}

func main() {
    nums := []int{1, 2, 3, 4, 5, 6, 7}
    root := sortedArrayToBST(nums)
    printBST(root)
    fmt.Println()
}

if len(nums) == 0 { return nil }

stop recursion when no elements left

mid := len(nums) / 2

find middle index to keep tree balanced

root := &TreeNode{Val: nums[mid]}

create root node with middle element

root.Left = sortedArrayToBST(nums[:mid])

build left subtree recursively from left half

root.Right = sortedArrayToBST(nums[mid+1:])

build right subtree recursively from right half

Output

1 2 3 4 5 6 7 

Complexity Analysis

Time: O(n) because each element is visited once to create nodes

Space: O(log n) due to recursion stack height for balanced tree

vs Alternative: Naive approach inserting nodes one by one into BST is O(n^2) for sorted input (skewed tree), much slower than this O(n) method

Edge Cases

empty array

returns nil tree (no nodes)

DSA Go

if len(nums) == 0 {
        return nil
    }

array with one element

creates single node tree

DSA Go

if len(nums) == 0 {
        return nil
    }

array with two elements

root is middle (second element), first element becomes left child

DSA Go

mid := len(nums) / 2

When to Use This Pattern

When you see a sorted array and need a balanced BST, use the middle element as root and recurse on halves to keep balance.

Common Mistakes

Mistake: Picking first or last element as root instead of middle
Fix: Always pick middle element to keep tree balanced

Mistake: Not handling empty array base case causing infinite recursion
Fix: Add base case to return nil when array is empty

Summary

Builds a balanced binary search tree from a sorted array by choosing middle elements as roots.

Use when you want a height-balanced BST from sorted data for efficient search.

The key is picking the middle element to keep left and right subtrees balanced.