<jupyter_start><jupyter_text>Min Height Bst[link](https://www.algoexpert.io/questions/Min%20Height%20BST)  My Solution<jupyter_code>def minHeightBst(array):
    return minHeightBstHelper(array, 0, len(array) - 1, None)

def minHeightBstHelper(array, minIdx, maxIdx, tree):
    if minIdx <= maxIdx:
        idx = (minIdx + maxIdx) // 2
        if tree is None:
            # for the root node
            tree = BST(array[idx])
        else:
            tree.insert(array[idx])
        minHeightBstHelper(array, minIdx, idx - 1, tree)
        minHeightBstHelper(array, idx + 1, maxIdx, tree)
    else:
        return
    return tree
    
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left is None:
                self.left = BST(value)
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BST(value)
            else:
                self.right.insert(value)

def minHeightBst(array):
    return minHeightBstHelper(array, 0, len(array) - 1)

def minHeightBstHelper(array, minIdx, maxIdx):
	if minIdx > maxIdx:
		return
	midIdx = (minIdx + maxIdx) // 2
	node = BST(array[midIdx])
	node.left = minHeightBstHelper(array, minIdx, midIdx - 1)
	node.right = minHeightBstHelper(array, midIdx + 1, maxIdx)
	return node

class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None<jupyter_output><empty_output><jupyter_text>Expert Solution<jupyter_code># O(nlog(n)) time | O(n) space - where n is the length of the array
def minHeightBst(array):
    return constructMinHeightBst(array, None, 0, len(array) - 1)

def constructMinHeightBst(array, bst, startIdx, endIdx):
    if startIdx < endIdx:
        return
    midIdx = (startIdx + endIdx) // 2
    valueToAdd = array[minIdx]
    if bst is None:
        bst = BST(valueToAdd)
    else:
        bst.insert(valueToAdd)
    constructMinHeightBst(array, bst, startIdx, midIdx - 1)
    constructMinHeightBst(array, bst, minIdx + 1, endIdx)
    return bst
    
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left is None:
                self.left = BST(value)
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BST(value)
            else:
                self.right.insert(value)

# O(n) time | O(n) space - where n is the length of the array
def minHeightBst(array):
    return constructMinHeightBst(array, None, 0, len(array) - 1)

def constructMinHeightBst(array, bst, startIdx, endIdx):
    if startIdx < endIdx:
        return
    midIdx = (startIdx + endIdx) // 2
    newBstNode = BST(array[midIdx])
    if bst is None:
        bst = newBstNode
    else:
        if array[midIdx] < bst.value:
            bst.left = newBstNode
            bst = bst.left
        else:
            bst.right = newBstNode
            bst = bst.right
    constructMinHeightBst(array, bst, startIdx, midIdx - 1)
    constructMinHeightBst(array, bst, minIdx + 1, endIdx)
    return bst
    
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# O(n) time | O(n) space - where n is the length of the array
def minHeightBst(array):
    return constructMinHeightBst(array, 0, len(array) - 1)

def constructMinHeightBst(array, startIdx, endIdx):
    if startIdx < endIdx:
        return None
    midIdx = (startIdx + endIdx) // 2
    bst = BST(array[midIdx])
    bst.left = constructMinHeightBst(array, startIdx, midIdx - 1)
    bst.right = constructMinHeightBst(array, minIdx + 1, endIdx)
    return bst
    
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10085679314565484, 'fraction_numerical': 0.007099143206854345, 'mean_word_length': 2.227488151658768, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 10, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '116295', 'license': 'MIT', 'n_tokens_mistral': 1394, 'n_tokens_neox': 1343, 'n_words': 352, 'path': 'algoExpert/min_height_bst/solution.ipynb', 'repo_name': 'maple1eaf/learning_algorithm', 'size': '4085'}