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.