BST data structure supports many dynamic-set operations including

1. Search
2. Minimum
3. Maximum
4. Predecessor
5. Successor
6. Insert
7. Delete

These basic operations allow us to treat this data structure both as a dictionary and as a priority queue.

Basic operations on a binary tree takes time proportional to the height of the tree, O(lg n) [worst case] and even O(n) if the tree is a linear chain.

Here I present a very basic version of binary tree written in python

def \_\_init\_\_(self,left=None,right=None,parent=None,key=None):
self.left = left
self.right = right
self.parent = parent
self.key = key

class BinaryTree:

def \_\_init\_\_(self):
self.root = None

def inorderWalk(self,node):
if node is not None:
self.inorderWalk(node.left)
print node.key
self.inorderWalk(node.right)

def treeSearch(self,node,key):
if node is None or key == node.key:
return node
if key < node.key:
return self.treeSearch(node.left,key)
else:
return self.treeSearch(node.right,key)

def iterativeTreeSearch(self,node,key):
while node is not None and key != node.key:
if key < node.key:
node = node.left
else:
node = node.right

return node

def treeMinimum(self,node):
while node.left is not None:
node = node.left

return node

def treeMaximum(self,node):
while node.right is not None:
node = node.right

return node

def treeSuccessor(self,node):
if node.right is not None:
return self.treeMinimum(node.right)
y = node.parent
while y is not None and node == y.right:
node = y
y = y.parent
return y

def treePredecessor(self,node):
if node.left is not None:
return self.treeMaximum(node.left)
y = node.parent
while y is not None and node == y.left:
node = y
y = y.parent
return y

def insert(self,node):
y = None
x = self.root
while x is not None:
y = x
if node.key < x.key:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node #Tree was empty
elif node.key < y.key:
y.left = node
else:
y.right = node

def transplant(self,u,v):
if u.parent is None:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
if v is not None:
v.parent = u.parent

def delete(self,node):
if node.left is None:
self.transplant(node,node.right)
elif node.right is None:
self.transplant(node,node.left)
else:
y = self.treeMinimum(node.right)
if y.parent is not node:
self.transplant(y,y.right)
y.right = node.right
y.right.parent = y
self.transplant(node,y)
y.left = node.left
y.left.parent = y

A = [12,5,2,9,18,15,19,13,17]

T = BinaryTree()

for \_key in A:
N = Node(key = \_key)
T.insert(N)

T.inorderWalk(T.root)

print "Max: " + str(T.treeMaximum(T.root).key)
print "Min: " + str(T.treeMinimum(T.root).key)

sn = T.treeSearch(T.root,17)

print T.treeSuccessor(sn).key
print T.treePredecessor(sn).key

# for k in A:
#     print "-"*10
#     f = T.treeSearch(T.root,k)
#     print "deleting", f.key
#     T.delete(f)
#     T.inorderWalk(T.root)