# 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.