Convert Sorted Array to Balanced BST in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced BST Inorder Traversal

Given the sorted array [1, 2, 3, 4, 5, 6, 7], a balanced BST is created by picking the middle element as root recursively. What is the inorder traversal output of the resulting BST?

DSA Go

package main

import "fmt"

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
}

func inorder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    left := inorder(root.Left)
    right := inorder(root.Right)
    return append(append(left, root.Val), right...)
}

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

A [3, 2, 1, 4, 5, 6, 7]

B [1, 2, 3, 4, 5, 6, 7]

C [7, 6, 5, 4, 3, 2, 1]

D [4, 2, 1, 3, 6, 5, 7]

💡 Hint

Inorder traversal of a BST always returns the sorted array.

The inorder traversal visits nodes in ascending order for a BST. Since the tree is built from a sorted array, the inorder traversal returns the original sorted array.

🧠 Conceptual

intermediate

Height of Balanced BST from Sorted Array

If you convert a sorted array of length 15 into a balanced BST by always choosing the middle element as root, what is the height of the resulting BST?

A 6

B 3

C 5

D 4

💡 Hint

Height of a balanced BST is about log2(n+1).

A balanced BST built from 15 nodes has height log2(15+1) = log2(16) = 4.

🔧 Debug

advanced

Identify the Bug in BST Construction

What error will this Go code produce when converting a sorted array to a balanced BST?

DSA Go

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-1])
    root.Right = sortedArrayToBST(nums[mid+1:])
    return root
}

A runtime error: slice bounds out of range

B nil pointer dereference

C compilation error: invalid slice index

D no error, runs correctly

💡 Hint

Check the slice indices carefully when slicing arrays.

The slice nums[:mid-1] causes a slice bounds out of range error when mid is 0 or 1 because mid-1 becomes negative or invalid.

🚀 Application

advanced

Number of Nodes in Left Subtree

Given a sorted array of length 9, after converting it to a balanced BST by choosing the middle element as root, how many nodes are in the left subtree of the root?

A 5

B 3

C 4

D 8

💡 Hint

Left subtree contains elements before the middle index.

For array length 9, middle index is 4 (0-based). Left subtree has elements at indices 0 to 3, total 4 nodes.

📝 Syntax

expert

Correct Go Syntax for Balanced BST Construction

Which option correctly implements the balanced BST construction from a sorted array in Go without syntax errors?

A

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
}

B

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-1])
    root.Right = sortedArrayToBST(nums[mid+1:])
    return root
}

C

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
}

D

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+1])
    root.Right = sortedArrayToBST(nums[mid+1:])
    return root
}

💡 Hint

Check slice indices carefully to avoid overlap or out of range.

Option A correctly slices left subtree as nums[:mid] and right subtree as nums[mid+1:], which covers all elements without overlap or missing elements.