Bird
Raised Fist0
DSA Goprogramming~5 mins

Convert Sorted Array to Balanced BST in DSA Go - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Convert Sorted Array to Balanced BST
O(n)
Understanding Time Complexity

We want to understand how the time needed to build a balanced binary search tree changes as the input array grows.

Specifically, how does the work increase when we convert a sorted array into a balanced BST?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


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
}

This code builds a balanced BST by choosing the middle element as root and recursively doing the same for left and right halves.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: Recursive calls splitting the array and creating nodes.
  • How many times: Each element is processed exactly once to create a node.
How Execution Grows With Input

Each recursive call splits the array roughly in half, and every element is visited once to create a node.

Input Size (n)Approx. Operations
10About 10 node creations and splits
100About 100 node creations and splits
1000About 1000 node creations and splits

Pattern observation: The work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the tree grows linearly with the number of elements in the array.

Common Mistake

[X] Wrong: "Because the function calls itself twice, the time complexity is exponential like O(2^n)."

[OK] Correct: Each element is processed only once, and the array is split, so the total work adds up linearly, not exponentially.

Interview Connect

Understanding this helps you explain how recursion and divide-and-conquer work together efficiently to build balanced trees.

Self-Check

"What if we did not pick the middle element but always picked the first element as root? How would the time complexity change?"

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard