# Binary Search Trees¶

In [64]:
class Node:
def __init__(self, key, parent=None, left=None, right=None, data=None):
self.key = key
self.p = parent
self.left = left
self.right = right
self.data = data

class BST:
def __init__(self, root):
self.root = root

In [65]:
node1 = Node(3)
node2 = Node(7)
node3 = Node(10)
node4 = Node(13)
node5 = Node(20)

node1.p = node2
node3.p = node2
node2.left = node1
node2.right = node3
node2.p = node4
node5.p = node4
node4.left = node2
node4.right = node5

bst = BST(node4)

In [49]:
def InorderTreeWalk(node):
if node:
InorderTreeWalk(node.left)
print(node.key)
InorderTreeWalk(node.right)

InorderTreeWalk(bst.root)

3
7
10
13
20

In [35]:
def TreeSearch(x, k):
if (x == None) or (k == x.key): return x
if k < x.key: return TreeSearch(x.left, k)
else: return TreeSearch(x.right, k)

In [40]:
TreeSearch(bst.root, 7) != None

Out[40]:
True
In [41]:
TreeSearch(bst.root, 8) != None

Out[41]:
False
In [38]:
def IterativeTreeSearch(x, k):
current = x
while current and k != current.key:
if k < current.key: current = current.left
else: current = current.right
return current

In [42]:
IterativeTreeSearch(bst.root, 7) != None

Out[42]:
True
In [43]:
TreeSearch(bst.root, 8) != None

Out[43]:
False
In [45]:
def TreeMinimum(x):
current = x
while current.left: current = current.left
return current

TreeMinimum(bst.root).key

Out[45]:
3
In [47]:
def TreeMaximum(x):
current = x
while current.right: current = current.right
return current

TreeMaximum(bst.root).key

Out[47]:
20
In [66]:
def TreeSuccessor(x):
if x.right: return TreeMinimum(x.right)
y = x.p
current = x
while y and current == y.right:
current = y
y = current.p
return y

In [67]:
TreeSuccessor(node1).key

Out[67]:
7
In [68]:
TreeSuccessor(node2).key

Out[68]:
10
In [70]:
TreeSuccessor(node5) == None

Out[70]:
True
In [73]:
def TreeInsert(T, z):
y = None
x = T.root
while x:
y = x
if z.key < x.key: x = x.left
else: x = x.right
z.p = y
if not y: T.root = x
else:
if z.key < y.key: y.left = z
else: y.right = z

In [75]:
TreeInsert(bst, Node(1))
TreeInsert(bst, Node(9))
InorderTreeWalk(bst.root)

1
3
7
9
10
13
20

In [ ]: