Building a Balanced BST from Sorted Data

If you insert sorted data into a regular BST, you get a linked list. Search goes from O(log n) to O(n). But there is a beautiful O(n) algorithm to build a perfectly balanced BST from sorted data using divide and conquer — pick the middle element as root, recurse on each half.

The problem with sorted insertion

Insert 1, 2, 3, 4, 5, 6, 7 into a BST one by one:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

Height: 6 (should be 2)
Search time: O(n) instead of O(log n)

Every new value is larger than all existing values, so it always goes to the rightmost position. The same happens with reverse-sorted or nearly-sorted data.

Balanced BST from sorted array

The divide-and-conquer approach is elegant: the middle element becomes the root, which guarantees equal-sized subtrees.

Algorithm

1. Find the middle element — make it the root
2. Recursively build the left subtree from the left half
3. Recursively build the right subtree from the right half

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sorted_array_to_bst(nums):
    """Convert sorted array to balanced BST (LeetCode 108)."""
    if not nums:
        return None

    def build(left, right):
        if left > right:
            return None

        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = build(left, mid - 1)
        node.right = build(mid + 1, right)
        return node

    return build(0, len(nums) - 1)

Time: O(n) — each element is visited exactly once. Space: O(log n) — recursion depth for a balanced tree.

Step-by-step walkthrough

nums = [1, 2, 3, 4, 5, 6, 7]

# build(0, 6): mid=3, root=4
#   build(0, 2): mid=1, root=2
#     build(0, 0): mid=0, root=1 (leaf)
#     build(2, 2): mid=2, root=3 (leaf)
#   build(4, 6): mid=5, root=6
#     build(4, 4): mid=4, root=5 (leaf)
#     build(6, 6): mid=6, root=7 (leaf)

# Result:
#        4
#       / \
#      2   6
#     / \ / \
#    1  3 5  7
#
# Height = 2 = floor(log2(7))
# Perfectly balanced!

Why the middle element?

Choosing the middle guarantees that:

• Left half has floor(n/2) elements
• Right half has floor(n/2) or ceil(n/2) - 1 elements
• The difference in subtree sizes is at most 1

This recursively ensures the tree has minimum height.

Left-biased vs right-biased

When the array has an even number of elements, there are two valid midpoints:

# For [1, 2, 3, 4]:
# mid = (0+3)//2 = 1 → root=2 (left-biased)
# mid = (0+3+1)//2 = 2 → root=3 (right-biased)

# Both produce valid balanced BSTs:
#    2          3
#   / \        / \
#  1   3      2   4
#       \    /
#        4  1

Both are correct. LeetCode accepts either.

Balanced BST from sorted linked list

With a linked list, we cannot access the middle element in O(1). Two approaches:

Approach 1: Convert to array first

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sorted_list_to_bst_array(head):
    """Convert sorted linked list to BST via array conversion."""
    # Step 1: Convert to array O(n)
    nums = []
    current = head
    while current:
        nums.append(current.val)
        current = current.next

    # Step 2: Use the array approach
    return sorted_array_to_bst(nums)

Time: O(n). Space: O(n) for the array.

Approach 2: Simulate inorder traversal (O(1) extra space)

This clever approach builds the tree in inorder sequence, advancing a pointer through the linked list simultaneously:

def sorted_list_to_bst(head):
    """Convert sorted linked list to balanced BST without array.
    LeetCode 109.
    """
    # Count nodes
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Use a mutable reference to track current list position
    current_node = [head]

    def build(left, right):
        if left > right:
            return None

        mid = (left + right) // 2

        # Build left subtree first (inorder: left → root → right)
        left_child = build(left, mid - 1)

        # Current list node IS the current tree node
        node = TreeNode(current_node[0].val)
        node.left = left_child
        current_node[0] = current_node[0].next  # advance list pointer

        # Build right subtree
        node.right = build(mid + 1, right)

        return node

    return build(0, length - 1)

Time: O(n). Space: O(log n) — only recursion stack, no array.

How does this work?

The key insight: an inorder traversal of a BST visits nodes in sorted order. We build the tree in inorder sequence, and the sorted linked list provides values in exactly that order.

List: 1 → 2 → 3 → 4 → 5 → 6 → 7

build(0, 6): mid=3
  build(0, 2): mid=1
    build(0, 0): mid=0
      build(0, -1) → None (left child)
      node = TreeNode(1), advance to 2    ← first list value
      build(1, -1) → None (right child)
      return node(1)
    node = TreeNode(2), advance to 3      ← second list value
    build(2, 2): mid=2
      ...returns node(3)                  ← third list value
    return node(2)
  node = TreeNode(4), advance to 5        ← fourth list value (root!)
  build(4, 6): mid=5
    ...builds subtree [5, 6, 7]
  return node(4)

Converting BST to sorted doubly-linked list

The reverse problem: flatten a BST into a sorted circular doubly-linked list (LeetCode 426).

In-place conversion

def bst_to_dll(root):
    """Convert BST to sorted circular doubly-linked list.
    Uses left as 'prev' and right as 'next'.
    Returns the head (smallest node).
    """
    if not root:
        return None

    first = [None]  # smallest node (head of DLL)
    last = [None]   # previous node during inorder

    def inorder(node):
        if not node:
            return

        inorder(node.left)

        # Process current node
        if last[0]:
            # Link previous node to current
            last[0].right = node
            node.left = last[0]
        else:
            # First node (smallest)
            first[0] = node

        last[0] = node

        inorder(node.right)

    inorder(root)

    # Make it circular
    first[0].left = last[0]
    last[0].right = first[0]

    return first[0]

Walkthrough

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

Inorder visit sequence: 1, 2, 3, 4, 5, 6, 7

After conversion (circular DLL):
... ↔ 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6 ↔ 7 ↔ ...
(7.right = 1, 1.left = 7)

Each node's 'left' is prev, 'right' is next.

Converting sorted DLL back to balanced BST

def dll_to_bst(head):
    """Convert sorted circular DLL back to balanced BST."""
    if not head:
        return None

    # Break the circular link and count nodes
    # Find tail
    tail = head.left
    tail.right = None
    head.left = None

    # Count nodes
    length = 0
    current = head
    while current:
        length += 1
        current = current.right

    # Build BST using the linked list approach
    current_node = [head]  # use head as starting point

    def build(left, right):
        if left > right:
            return None

        mid = (left + right) // 2
        left_child = build(left, mid - 1)

        node = current_node[0]
        node.left = left_child
        current_node[0] = current_node[0].right

        node.right = build(mid + 1, right)
        return node

    return build(0, length - 1)

Rebalancing an existing BST

Given an unbalanced BST, convert it to a balanced one (LeetCode 1382).

Approach 1: Inorder to array, then rebuild

def balance_bst(root):
    """Rebalance an existing BST."""
    # Step 1: Get sorted values via inorder traversal
    values = []
    def inorder(node):
        if node:
            inorder(node.left)
            values.append(node.val)
            inorder(node.right)
    inorder(root)

    # Step 2: Build balanced BST from sorted array
    return sorted_array_to_bst(values)

Time: O(n). Space: O(n) for the array.

Approach 2: Day-Stout-Warren algorithm (in-place)

The Day-Stout-Warren (DSW) algorithm rebalances a BST in-place using O(1) extra space. It works in three phases:

1. Flatten the BST into a “vine” (right-only linked list) using right rotations
2. Count the nodes
3. Compress the vine into a balanced tree using left rotations

def dsw_balance(root):
    """Day-Stout-Warren algorithm for in-place BST rebalancing."""
    import math

    # Create a dummy root
    dummy = TreeNode(0)
    dummy.right = root

    # Phase 1: Tree to vine (right-leaning linked list)
    def tree_to_vine(root):
        """Flatten tree to vine using right rotations."""
        count = 0
        tail = root
        rest = tail.right

        while rest:
            if rest.left is None:
                tail = rest
                rest = rest.right
                count += 1
            else:
                # Right rotate
                temp = rest.left
                rest.left = temp.right
                temp.right = rest
                rest = temp
                tail.right = temp

        return count

    # Phase 2: Vine to balanced tree using left rotations
    def compress(root, count):
        """Perform 'count' left rotations starting from root."""
        scanner = root
        for _ in range(count):
            child = scanner.right
            scanner.right = child.right
            scanner = scanner.right
            child.right = scanner.left
            scanner.left = child

    node_count = tree_to_vine(dummy)

    # Phase 3: Calculate rotations needed
    # Number of nodes in the "full" part of the tree
    leaves = node_count + 1 - 2 ** int(math.log2(node_count + 1))
    compress(dummy, leaves)
    node_count -= leaves

    while node_count > 1:
        compress(dummy, node_count // 2)
        node_count //= 2

    return dummy.right

DSW walkthrough

Unbalanced BST:
1
 \
  2
   \
    3
     \
      4
       \
        5

Phase 1 (tree to vine): already a vine! count = 5

Phase 2 (vine to balanced):
leaves = 5 + 1 - 2^2 = 6 - 4 = 2
compress(dummy, 2): 2 left rotations

After first compression:
    2
   / \
  1   4
     / \
    3   5

compress(dummy, 1): 1 left rotation (at higher level... already close)

Final balanced tree:
      3        (or similar balanced shape)
     / \
    2   4
   /     \
  1       5

Height = 2 = floor(log2(5))

Time: O(n). Space: O(1) — truly in-place!

Merge two BSTs into one balanced BST

def merge_bsts(root1, root2):
    """Merge two BSTs into one balanced BST."""
    # Step 1: Get sorted arrays from both BSTs
    def inorder(node, result):
        if node:
            inorder(node.left, result)
            result.append(node.val)
            inorder(node.right, result)

    arr1, arr2 = [], []
    inorder(root1, arr1)
    inorder(root2, arr2)

    # Step 2: Merge two sorted arrays
    merged = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])

    # Step 3: Build balanced BST from merged sorted array
    return sorted_array_to_bst(merged)

Time: O(m + n) where m and n are the sizes of the two BSTs.

Verify balance

A helper to check if a BST is balanced:

def is_balanced(root):
    """Check if tree is height-balanced (LeetCode 110)."""
    def check(node):
        if not node:
            return 0

        left_h = check(node.left)
        if left_h == -1:
            return -1

        right_h = check(node.right)
        if right_h == -1:
            return -1

        if abs(left_h - right_h) > 1:
            return -1

        return 1 + max(left_h, right_h)

    return check(root) != -1

Complete test

# Test sorted array to BST
nums = list(range(1, 16))  # [1, 2, ..., 15]
root = sorted_array_to_bst(nums)

# Verify
print(is_balanced(root))  # True

# Check inorder produces sorted output
def get_inorder(node):
    if not node:
        return []
    return get_inorder(node.left) + [node.val] + get_inorder(node.right)

print(get_inorder(root) == nums)  # True

# Check height
def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

print(height(root))  # 4 (log2(15) ≈ 3.9)

When to use each approach

Scenario	Approach	Time	Space
Sorted array to BST	Divide and conquer	O(n)	O(log n)
Sorted linked list to BST	Inorder simulation	O(n)	O(log n)
Rebalance existing BST	Inorder + rebuild	O(n)	O(n)
Rebalance in-place	Day-Stout-Warren	O(n)	O(1)
Merge two BSTs	Inorder both + merge + build	O(m+n)	O(m+n)

Practice problems

1. Convert Sorted Array to BST (LeetCode 108) — The classic
2. Convert Sorted List to BST (LeetCode 109) — Linked list version
3. Balance a BST (LeetCode 1382) — Rebalance existing BST
4. Check if Balanced (LeetCode 110) — Verify the result
5. Flatten BST to Sorted List (LeetCode 897) — BST to linked list
6. All Elements in Two BSTs (LeetCode 1305) — Merge sorted traversals
7. Convert BST to Doubly Linked List (LeetCode 426)
8. Minimum Height Trees (LeetCode 310) — Related concept

Key takeaways

• Sorted data kills BST performance — always build from the middle, not sequentially
• Divide and conquer on sorted arrays produces perfectly balanced BSTs in O(n)
• For sorted linked lists, simulate inorder traversal to avoid O(n) random access
• BST to sorted DLL is an inorder traversal that links nodes as it visits them
• Day-Stout-Warren is the only O(1) space rebalancing algorithm
• The pattern “inorder to array, rebuild from middle” solves many BST restructuring problems