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.

Delete this entry (admin only).