Algorithms/util_tree.py at master · nadeesha90/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class node:
    def __init__(self,val=0):
        self.val = val
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.val)

def arrtoBST(nums,T):
    mid = int(len(nums)/2)
    left = nums[:mid]
    right = nums[mid+1:]

    T.val = nums[mid]
    if len(left) > 0:
        T.left = TreeNode(0)
        arrtoBST(left,T.left)

    if len(right) > 0:
        T.right = TreeNode(0)
        arrtoBST(right,T.right)

def inorder_traverse(root):
    if root != None:
        print str(root)
        inorder_traverse(root.left)
        inorder_traverse(root.right)

def construct_tree(values):
    if len(values) == 1:
        root = node(values[0])
    elif len(values) == 2:
        root = node(values[0])
        root.left = construct_tree(values[1:])
    elif len(values) > 2:
        root = node(values[0])
        l = len(values)-1
        left_values = values[1:1+l//2]
        right_values = values[1+l//2:]
        root.left = construct_tree(left_values)
        root.right = construct_tree(right_values)
    else:
        root = None

    return root

if __name__ == '__main__':
    values = [1]*10
    root = construct_tree(values)
    inorder_traverse(root)