Convert Sorted Array to Binary Search Tree

class Solution {
public:
    TreeNode* transformSortedArrayToBST(vector<int>& arr) {
        return buildBST(arr, 0, arr.size() - 1);
    }

private:
    TreeNode* buildBST(vector<int>& arr, int start, int end) {
        if (start > end) return nullptr;
        int middle = (start + end) / 2;
        if ((start + end) % 2 == 1) middle += rand() % 2;
        TreeNode* node = new TreeNode(arr[middle]);
        node->left = buildBST(arr, start, middle - 1);
        node->right = buildBST(arr, middle + 1, end);
        return node;
    }
};

To convert a sorted array into a balanced binary search tree (BST), create a function in C++ that employs recursion to find the middle element of the array, inserting it as a node and recursively building the left subtree from the elements before the middle and the right subtree from the elements after the middle. Implement this by defining a class Solution with two functions:

• transformSortedArrayToBST which acts as the main function and initiates the BST transformation process with boundary indices.
• buildBST, a private recursive helper function that divides the array and creates a TreeNode at each division:
  • Determine the base condition where the start index exceeds the end index, returning nullptr.
  • Calculate the mid-point. If the index sum is odd, apply a random adjustment to ensure balance.
  • Recursively allocate nodes to the left child and right child of the current TreeNode.

The program effectively uses the properties of the sorted array to ensure each subtree node is inserted at its correct position, thus maintaining the characteristic of the binary search tree. The randomness in selecting the middle index aids in maintaining balance, especially useful in scenarios where distinct set-ups might cause imbalances in tree structure. This solution provides an efficient and straightforward approach to construct a balanced BST, leveraging the binary search principle.

class Solution {
    int[] elements;
    Random randomGenerator = new Random();

    public TreeNode constructBST(int start, int end) {
        if (start > end) return null;

        // Pick a random index for the root
        int midpoint = (start + end) / 2;
        if ((start + end) % 2 == 1) midpoint += randomGenerator.nextInt(2);

        // Build the tree node by node
        TreeNode rootNode = new TreeNode(elements[midpoint]);
        rootNode.left = constructBST(start, midpoint - 1);
        rootNode.right = constructBST(midpoint + 1, end);
        return rootNode;
    }

    public TreeNode sortedArrayToBST(int[] elements) {
        this.elements = elements;
        return constructBST(0, elements.length - 1);
    }
}

The provided Java solution efficiently demonstrates how to convert a sorted array into a balanced Binary Search Tree (BST). The process implemented in the code ensures that the tree remains balanced, thus maintaining optimal search operations.

• The Solution class stores the array elements in a private elements array and includes a randomGenerator to help vary the choice of the root node slightly by randomness when the array length is odd.
• The constructBST function recursively creates the BST:
  1. Base case: if the start index is greater than the end index, the recursion halts, returning null – indicative of no subtree.
  2. A root node is chosen using a combination of midpoint calculation and an optional random adjustment to balance the tree and to avoid skewed tree structures, especially useful in scenarios involving sorted data.
  3. Recursion continues to construct the left subtree using the sub-array to the left of the midpoint and the right subtree using the sub-array on the right.
• The sortedArrayToBST function sets up the initial state by storing the reference to the input array and calling the constructBST function with indices covering the entire range of the array.

Thanks to the smart midpoint selection randomized slightly, this algorithm focuses not only on the BST property but also emphasizes maintaining a balance, resulting in a logarithmic height in expectation, conducive to efficient operations like lookups, insertions, and deletions.

struct TreeNode* buildBST(int* elements, int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    if ((start + end) % 2) mid += rand() % 2;
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = elements[mid];
    node->left = buildBST(elements, start, mid - 1);
    node->right = buildBST(elements, mid + 1, end);
    return node;
}
struct TreeNode* convertSortedArrayToBST(int* elements, int size) {
    return buildBST(elements, 0, size - 1);
}

To convert a sorted array into a binary search tree (BST) using C programming, follow the efficient approach implemented in the provided code. The process delves into two primary functions: buildBST and convertSortedArrayToBST.

• buildBST takes an array of integers (elements), the start index (start), and the end index (end):

  1. Check for the base condition where start exceeds end. If true, return NULL indicating there's no subtree to process in this segment.
  2. Calculate the middle index (mid) to use as a root for the BST node. Adjustments include adding a random offset to promote balance in the tree when there's a choice of two middle values.
  3. Dynamically allocate a new tree node (node) and set its value to the element at the mid index.
  4. Recursively build the left subtree using elements from the start to mid - 1.
  5. Similarly, build the right subtree using elements from mid + 1 to end.
  6. Return the constructed node, now representing the root of the BST for the given segment.

• convertSortedArrayToBST initiates the tree construction:

  1. It simply calls the buildBST function passing the entire array and its size to cover all elements.

Ensure the development environment supports C standard library for dynamic memory management (malloc) and random number generation (rand()). The approach taken in the script ensures the constructed BST adheres to properties of a balanced binary search tree, where heights of two child subtrees of any node differ at most by one.

var sortedArrayToBST = function (arr) {
    let constructTree = function (start, end) {
        if (start > end) return null;
        let mid = Math.floor((start + end) / 2);
        if ((start + end) % 2 === 1) mid += Math.floor(Math.random() * 2);
        let node = new TreeNode(arr[mid]);
        node.left = constructTree(start, mid - 1);
        node.right = constructTree(mid + 1, end);
        return node;
    };
    return constructTree(0, arr.length - 1);
};

This JavaScript code defines a function sortedArrayToBST that constructs a balanced binary search tree (BST) from a sorted array. The process involves recursively picking the middle element of the array to ensure the resulting tree remains balanced. Here's a summary of the function execution:

• Define the function sortedArrayToBST which takes the sorted array arr as input.
• Inside, define a helper function constructTree that takes two parameters, start and end, representing the current segment of the array being processed.
• Check if start is greater than end. If true, return null, as this indicates that there are no elements to process in this segment.
• Calculate the mid index of the segment. If the subsection length is odd, the middle index is adjusted randomly by 0 or 1 to enhance balance.
• Create a new tree node TreeNode with the element at the mid index.
• Recursively set the left child of the node by processing the subarray before mid.
• Recursively set the right child by processing the subarray after mid.
• The constructTree function returns the node.
• The sortedArrayToBST function initializes the recursive construction by calling constructTree with the indices 0 and arr.length - 1.
• Finally, it returns the root of the constructed BST.

The approach cleverly manipulates the middle index under certain conditions to potentially improve the balance of the tree resulting from uneven array lengths. The recursion ensures each segment of the array correctly contributes to the corresponding subtree of the BST.

from random import choice

class Solution:
    def convertSortedArrayToBST(self, values: List[int]) -> TreeNode:
        def construct_bst(start, end):
            if start > end:
                return None
            
            # Selecting a central node randomly if possible
            mid = (start + end) // 2
            if (start + end) % 2 == 1:
                mid += choice([0, 1])
            
            # Recursive tree creation: node -> left -> right
            node = TreeNode(values[mid])
            node.left = construct_bst(start, mid - 1)
            node.right = construct_bst(mid + 1, end)
            return node
        
        return construct_bst(0, len(values) - 1)

The provided Python code defines a method for converting a sorted array into a binary search tree. This transformation is crucial for operations requiring binary search properties to optimize search queries, such as lookups, insertions, and deletions in logarithmic time.

The convertSortedArrayToBST function employs a recursive helper function construct_bst to perform this conversion:

1. Checking Base Conditions: If the start index exceeds the end, the recursion stops and returns None, indicating no subtree is possible with the given indices.
2. Selecting the Root Node: Calculate the middle index mid between start and end. If the sum of start and end is odd, adjust mid randomly by either 0 or 1 to maintain balance in the tree.
3. Creating the Tree Node: Instantiate a TreeNode with the element at the index mid of the array. This node acts as the root for the current subtree.
4. Recursive Tree Construction: Set the left child of the node by recursively calling construct_bst from start to mid - 1 and the right child from mid + 1 to end.

The approach ensures each node of the final tree adheres to the properties of a binary search tree by using the middle of each sub-array slice, optionally adjusted for randomness. This division ensures both the left and right subtrees contain approximately the same number of nodes, supporting tree balance.