# Demo entry 6442305

**python**

Submitted by **anonymous**
on May 27, 2017 at 04:39

Language: Python. Code size: 1.5 kB.

""" CBEPGC in: sorted list out: bst with minimal height #? duplicates? inductive case: if I have a sorted list I can insert the middle value in the tree and make two subtrees of minimal height on each side of it base: a sorted list of size 1 makes a tree of min height """ class Node(object): def __init__(self, val): self.val = val self.left = None self.right = None def minTree(inpt): length = len(inpt) return minTreeHelper(inpt, 0, length-1) def minTreeHelper(inpt, low, high): length = (high-low)+1 if length == 1: return Node(inpt[low]) if length <= 0: return None mid = (low+high)/2 #(hi-low)/2 +low middleNode = Node(inpt[mid]) leftNode = minTreeHelper(inpt, low, mid-1) rightNode = minTreeHelper(inpt, mid+1, high) middleNode.left = leftNode middleNode.right = rightNode return middleNode def printInOrder(curr, lst, height): if not curr: return printInOrder(curr.left, lst, height+1) #print curr.left.val lst.append((curr.val, height)) print curr.val printInOrder(curr.right, lst, height+1) #print curr.right.val if __name__ == "__main__": node = minTree([2,4,6,8,10]) print node, node.left.val, node.right.val lst = [] printInOrder(node, lst, 0) node1 = node print lst node1.val = 5 print node1 == node print node.val #assert(lst == [2,4,6,8,10])

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.