Convert Sorted Array to Balanced BST in DSA Go - Build from Scratch

Convert Sorted Array to Balanced BST

📖 Scenario: You have a sorted list of numbers representing data that needs to be organized for fast searching. A balanced Binary Search Tree (BST) is a great way to do this because it keeps the data sorted and allows quick lookups.Imagine you are building a phone book app that needs to quickly find contacts by their phone numbers. You want to convert the sorted list of phone numbers into a balanced BST.

🎯 Goal: Build a balanced BST from a sorted array of integers. The BST should be balanced so that searching is efficient.

📋 What You'll Learn

Create a sorted array of integers named nums with values 1, 2, 3, 4, 5, 6, 7

Create a struct type TreeNode with Val (int), Left, and Right pointers

Write a recursive function sortedArrayToBST that takes nums []int and returns *TreeNode

Print the BST nodes in-order to show the balanced tree structure

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases and search engines to organize data for fast searching and retrieval.

💼 Career

Understanding BSTs and recursion is important for software engineers working on data structures, algorithms, and performance optimization.

1

Create the sorted array

Create a sorted array of integers called nums with these exact values: 1, 2, 3, 4, 5, 6, 7

DSA Go

// Create the sorted array nums with values 1 to 7
// Your code here

Hint

Use nums := []int{1, 2, 3, 4, 5, 6, 7} to create the array.

2

Define the TreeNode struct

Define a struct type called TreeNode with three fields: Val int, Left *TreeNode, and Right *TreeNode

DSA Go

package main

// Define TreeNode struct here
// Your code here

func main() {
    nums := []int{1, 2, 3, 4, 5, 6, 7}
}

Hint

Use type TreeNode struct { Val int; Left *TreeNode; Right *TreeNode }.

3

Write the recursive function to build BST

Write a recursive function called sortedArrayToBST that takes nums []int and returns *TreeNode. It should find the middle element as root, recursively build left and right subtrees from the left and right halves of the array.

DSA Go

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Write sortedArrayToBST function here
// Your code here

func main() {
    nums := []int{1, 2, 3, 4, 5, 6, 7}
}

Hint

Use the middle element as root, then call sortedArrayToBST recursively on left and right slices.

4

Print the BST in-order

Write a function called inOrder that takes root *TreeNode and prints the node values in ascending order separated by spaces. Then call inOrder with the BST created from nums inside main.

DSA Go

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

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
}

// Write inOrder function here
// Your code here

func main() {
    nums := []int{1, 2, 3, 4, 5, 6, 7}
    // Call sortedArrayToBST and inOrder here
    // Your code here
}

Hint

Use in-order traversal to print nodes in ascending order.

Practice

1. What is the main goal when converting a sorted array to a balanced Binary Search Tree (BST)?

easy

A. To create a BST with minimal height for efficient search

B. To create a linked list from the array

C. To reverse the array elements

D. To sort the array again

Solution

1. Step 1: Understand the problem goal

   The goal is to build a BST that is balanced, meaning the tree height is minimized to allow fast searching.

2. Step 2: Why minimal height matters

   A balanced BST ensures operations like search, insert, and delete run in O(log n) time, which is efficient.

3. Final Answer:

   To create a BST with minimal height for efficient search -> Option A

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

Hint: Pick option about minimal height for balanced BST [OK]

Common Mistakes:

• Confusing BST with linked list
• Thinking sorting again is needed
• Ignoring tree balance importance

2. Which Go function signature correctly represents the recursive function to convert a sorted array to a balanced BST?

easy

A. func sortedArrayToBST(nums []int) *TreeNode

B. func sortedArrayToBST(nums int) TreeNode

C. func sortedArrayToBST(nums []int) int

D. func sortedArrayToBST(nums []int) []int

Solution

1. Step 1: Identify input and output types

   The function takes a slice of integers (sorted array) and returns a pointer to the root TreeNode of the BST.

2. Step 2: Match correct Go syntax

   func sortedArrayToBST(nums []int) *TreeNode matches: input is []int, output is *TreeNode pointer, which is standard for tree nodes in Go.

3. Final Answer:

   func sortedArrayToBST(nums []int) *TreeNode -> Option A

4. Quick Check:

   Input []int, output *TreeNode pointer [OK]

Hint: Look for slice input and pointer to TreeNode output [OK]

Common Mistakes:

• Using int instead of slice for input
• Returning int or slice instead of TreeNode pointer
• Missing pointer in return type

3. Given the sorted array [1, 2, 3, 4, 5], what is the root value of the balanced BST created by the standard algorithm?

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Find middle element of array

   The middle index of [1, 2, 3, 4, 5] is 2 (0-based), so middle element is 3.

2. Step 2: Root is middle element

   The root of the balanced BST is the middle element to balance left and right subtrees.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Middle element = root = 3 [OK]

Hint: Root is middle element of sorted array [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one error in middle index
• Confusing index with value

4. Consider this Go code snippet to convert 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:])
    return root
}

What is the bug in this code?

medium

A. The function should return an int, not *TreeNode

B. The base case should check for len(nums) < 0

C. The root node is created with wrong value

D. The right subtree slice should start from mid+1, not mid

Solution

1. Step 1: Analyze slicing for right subtree

   The right subtree slice uses nums[mid:], which includes the middle element again, causing duplicate nodes.

2. Step 2: Correct slice to exclude middle element

   Right subtree should start from mid+1 to avoid including root again.

3. Final Answer:

   The right subtree slice should start from mid+1, not mid -> Option D

4. Quick Check:

   Right slice = nums[mid+1:] to avoid duplicates [OK]

Hint: Right slice must exclude middle element by starting at mid+1 [OK]

Common Mistakes:

• Using mid instead of mid+1 for right slice
• Wrong base case condition
• Returning wrong type

5. You have a sorted array [10, 20, 30, 40, 50, 60, 70]. After converting it to a balanced BST, what is the inorder traversal of the BST?

hard

A. [10, 30, 20, 50, 40, 70, 60]

B. [10, 20, 30, 40, 50, 60, 70]

C. [70, 60, 50, 40, 30, 20, 10]

D. [40, 20, 10, 30, 60, 50, 70]

Solution

1. Step 1: Understand inorder traversal of BST

   Inorder traversal visits nodes in ascending order for BST, so it returns the sorted array.

2. Step 2: Confirm traversal matches original array

   Since the BST is built from sorted array, inorder traversal outputs the same sorted sequence.

3. Final Answer:

   [10, 20, 30, 40, 50, 60, 70] -> Option B

4. Quick Check:

   Inorder traversal = sorted array [OK]

Hint: Inorder traversal of BST equals sorted array [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Assuming traversal changes order
• Mixing up traversal outputs