NUHMAN.com

Introduction

LeetCode 108: Convert Sorted Array to Binary Search Tree asks you to convert a sorted array into a Binary Search Tree (BST). The resulting BST must be height-balanced. This problem is a classic example of how to construct a balanced binary tree from a sorted array.

The key insight for this problem is that for a binary search tree to be balanced, its root should be chosen from the middle element of the array. The elements to the left of the middle form the left subtree, and the elements to the right form the right subtree. This strategy leads to an optimal solution using the Divide and Conquer technique.

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Example:

go

Input: nums = [-10,-3,0,5,9]
Output:
    [0,-3,9,-10,null,5]

Approach:

Divide and Conquer Strategy

We can use a Divide and Conquer approach to construct the binary search tree from the sorted array:

1. Base Case: If the array is empty, return nil (i.e., the tree is empty).
2. Recursive Case:

• Select the middle element of the array as the root of the BST.
• Recursively build the left subtree using the left half of the array.
• Recursively build the right subtree using the right half of the array.

This approach ensures that the tree is height-balanced because we always choose the middle element as the root, leading to roughly equal-sized left and right subtrees.

Go Implementation

Solution Using Divide and Conquer

go

package main

// TreeNode represents a node in the binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// sortedArrayToBST converts a sorted array to a height-balanced binary search tree.
func sortedArrayToBST(nums []int) *TreeNode {
    return buildTree(nums, 0, len(nums)-1)
}

// buildTree is a helper function that recursively builds the tree.
func buildTree(nums []int, left, right int) *TreeNode {
    if left > right {
        return nil
    }

    // Find the middle element to maintain balance.
    mid := (left + right) / 2

    // Create a new node with the middle element as the root.
    node := &TreeNode{Val: nums[mid]}

    // Recursively build the left and right subtrees.
    node.Left = buildTree(nums, left, mid-1)
    node.Right = buildTree(nums, mid+1, right)

    return node
}

Explanation:

1. TreeNode Structure:

• The TreeNode struct represents a node in the binary tree. Each node has a value (Val), and pointers to its left and right children (Left and Right).

1. sortedArrayToBST Function:

• This is the main function that takes the sorted array nums and calls the helper function buildTree to construct the BST. The helper function is passed the current range of the array (from left to right indices).

1. buildTree Function:

• This function recursively builds the binary search tree:
• Base Case: If the left index is greater than the right index, return nil (indicating no nodes left to process).
• Recursive Case:
• Find the middle element using the formula mid = (left + right) / 2.
• Create a new tree node with the middle element as the value.
• Recursively build the left and right subtrees by calling buildTree on the left and right halves of the array.
• Return the current node after the left and right children are assigned.

1. Balanced Tree Construction:

• By always selecting the middle element as the root, we ensure that the tree remains balanced, as each recursive step divides the problem into two roughly equal halves.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where:

• n is the number of nodes in the binary tree (or the length of the input array).

Time Complexity:

• In each recursive call, we process one element from the array and divide the array into two halves. Since we process each element exactly once, the time complexity is O(n).

Space Complexity:

• The space complexity is O(n) due to the recursion stack. In the worst case, the recursion depth is equal to the height of the tree, which is O(log n) for a balanced tree, but we must also account for the space needed to store the tree nodes, resulting in O(n) overall.

Edge Cases

1. Empty Array:

• Input: nums = []
• Output: nil
• Explanation: An empty array results in an empty tree.

1. Single Element Array:

• Input: nums = [1]
• Output: [1]
• Explanation: A single-element array results in a tree with just one node.

1. Array with Multiple Elements:

• Input: nums = [-10,-3,0,5,9]
• Output: [0,-3,9,-10,null,5]
• Explanation: The function will select the middle element of the array (0) as the root, recursively build the left and right subtrees, and return the balanced binary search tree.

Conclusion

LeetCode 108: Convert Sorted Array to Binary Search Tree is a problem that requires constructing a height-balanced binary search tree from a sorted array. By employing the Divide and Conquer approach, where we recursively select the middle element of the array as the root, we can efficiently build a balanced tree with a time complexity of O(n). This problem is a great exercise in tree construction and understanding recursion in binary trees.