Convert Sorted Array To Binary Search Tree

                                            
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) {
            return nullptr;
        }
        return helper(nums, 0, nums.size() - 1);
    }
    
    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return convertToBST(nums, 0, nums.length - 1);
    }
    
    private TreeNode convertToBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = convertToBST(nums, start, mid - 1);
        node.right = convertToBST(nums, mid + 1, end);
        
        return node;
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
    
class Solution(object):
    def sortedArrayToBST(self, nums):
        if not nums:
            return None
        
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        
        return root

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    if(numsSize == 0) return NULL;
    
    int mid = numsSize / 2;
    
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[mid];
    
    root->left = sortedArrayToBST(nums, mid);
    root->right = sortedArrayToBST(nums + mid + 1, numsSize - mid - 1);
    
    return root;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        if(nums == null || nums.Length == 0) {
            return null;
        }
        return BuildTree(nums, 0, nums.Length - 1);
    }
    
    private TreeNode BuildTree(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        
        node.left = BuildTree(nums, left, mid - 1);
        node.right = BuildTree(nums, mid + 1, right);
        
        return node;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 *
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if (nums.length === 0) return null;
    
    const mid = Math.floor(nums.length / 2);
    const node = new TreeNode(nums[mid]);
    
    node.left = sortedArrayToBST(nums.slice(0, mid));
    node.right = sortedArrayToBST(nums.slice(mid + 1));
    
    return node;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function sortedArrayToBST(nums: number[]): TreeNode | null {
    if (nums.length === 0) return null;
    const mid = Math.floor(nums.length / 2);
    const root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1));
    return root;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) {
 *         $this->val = $value;
 *     }
 * }
 */
class Solution {
    /**
     * @param Integer[] $nums
     * @return TreeNode
     */
    function sortedArrayToBST($nums) {
        if (empty($nums)) {
            return null;
        }
        
        $mid = (int)(count($nums) / 2);
        
        $root = new TreeNode($nums[$mid]);
        
        $root->left = $this->sortedArrayToBST(array_slice($nums, 0, $mid));
        $root->right = $this->sortedArrayToBST(array_slice($nums, $mid+1));
        
        return $root;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        if nums.isEmpty {
            return nil
        }
        let mid = nums.count / 2
        let node = TreeNode(nums[mid])
        node.left = sortedArrayToBST(Array(nums[0..<mid]))
        node.right = sortedArrayToBST(Array(nums[(mid + 1)...]))
        return node
    }
}

                                            
/**
 * Definition for a binary tree node.
 * 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
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def sorted_array_to_bst(nums)
    return nil if nums.empty?
    
    mid = nums.length / 2
    
    node = TreeNode.new(nums[mid])
    node.left = sorted_array_to_bst(nums[0...mid])
    node.right = sorted_array_to_bst(nums[mid+1..-1])
    
    return node
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode 
= null, _right: TreeNode = null) {
 */
object Solution {
    def sortedArrayToBST(nums: Array[Int]): TreeNode = {
        def helper(left: Int, right: Int): TreeNode = {
            if (left > right) return null
            val mid = left + (right - left) / 2
            val root = new TreeNode(nums(mid))
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            root
        }
        helper(0, nums.length - 1)
    }
}

To solve this coding challenge, you need to convert a sorted array into a height-balanced binary search tree (BST). The key to achieving a height-balanced BST is to always select the middle element of the current segment of the array as the root of the subtree. This approach ensures that the tree remains balanced as the left and right subtrees will have approximately the same number of nodes. Now, let's break down the problem and explain the solution step-by-step.

Explanation

Understanding the Problem :

You're given a sorted array, which is ordered in ascending fashion.
You need to convert this array into a height-balanced binary search tree (BST).
A height-balanced BST is one where the depths of the two subtrees of every node never differ by more than one.
The middle element of any sub-array will act as the root since it ensures even distribution of elements to the left and right subtrees.

High-Level Solution Approach :

Use a recursive approach to build the tree.
Find the middle element of the current sublist (array slice) and make it the root node.
Recursively repeat the process for the left sublist (elements before the middle element) to build the left subtree.
Recursively apply the same process for the right sublist (elements after the middle element) to build the right subtree.

Steps to Implement :

If the input list is empty, return
None

(base case).
Find the middle index of the list.
Create a tree node with the value at the middle index.
Recursively build the left subtree using the left part of the list.
Recursively build the right subtree using the right part of the list.
Return the constructed tree node (which serves as the root).

Detailed Steps in Pseudocode

Here we delve into the more granular steps of the algorithm with pseudocode:

Base Case :

If the current sub-array (slice of array) is empty, return
None

.

Recursive Case :

Calculate the middle index of the current sub-array.
Create a new tree node with the middle element's value.
Recursively create the left subtree by passing the left sub-array (elements before the middle index) to the same function.
Recursively create the right subtree by passing the right sub-array (elements after the middle index) to the same function.
Link these subtrees to the current node's left and right pointers respectively.
Return the current node as the root of the subtree.

Here is the pseudocode encapsulating the above logic:

                                            
# Define the TreeNode structure
# TreeNode:
#     value: int
#     left: TreeNode
#     right: TreeNode

# Function to convert sorted array to BST
FUNCTION sortedArrayToBST(nums):
    # Base case: if the array is empty
    IF nums IS EMPTY:
        RETURN None

    # Find the middle index of the array
    mid_index = LENGTH(nums) // 2
    
    # Create a new TreeNode with the middle element's value
    root_node = TreeNode(nums[mid_index])
    
    # Recursively build the left subtree with elements left of the middle
    root_node.left = sortedArrayToBST(nums[0:mid_index])
    
    # Recursively build the right subtree with elements right of the middle
    root_node.right = sortedArrayToBST(nums[mid_index+1:])
    
    # Return the root node of this subtree
    RETURN root_node

This pseudocode constructs a height-balanced BST by making sure every call to

sortedArrayToBST()

divides the input array into two halves, using the middle element as the root, thus ensuring the balance. This maintains the depth property of a BST so that no two leaves' depths differ by more than one. By consistently following this division, you ensure that the tree remains balanced and adheres to the BST properties.