daily_questions/binarySearchTree.py at master · dlefcoe/daily_questions · 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
'''

This problem was asked by LinkedIn.

Determine whether a tree is a valid binary search tree.

A binary search tree is a tree with two children, left and right,
and satisfies the constraint that the key in the left child must be less
than or equal to the root and the key in the right child must be greater than or equal to the root.

'''

# %%

import random as rnd


class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

    def makeRight(self, r):
        self.right = Node(r)
        # condition that right node >= root
        if r < self.val:
            self.right = self.val

    def makeLeft(self, l):
        self.left = Node(l)
        # condition that left node <= root
        if l > self.val:
            self.left = self.val


# make binary tree

# root of tree
root = Node(100)


# left side
root.makeLeft(rnd.randint(0,200))
root.left = Node(rnd.randint(0,200))
root.left.makeLeft(rnd.randint(0,200))
root.left.makeRight(rnd.randint(0,200))

'''
root.left = Node(90)
root.left.left = Node(80)
root.left.right = Node(95)
'''

# right side
root.right = Node(110)
root.right.right = Node(120)
root.right.left = Node(105)


'''
root.makeLeft(99)
root.makeRight(101)
'''


# print root of tree
print(root.val, root.left.val, root.right.val)

# print second (left) level of tree
print(root.left.val, root.left.left, root.left.right)

# print second (right) level of tree
print(root.right.val, root.right.left.val, root.right.right.val)


# now check the tree