# Binary Search Trees¶

## Agenda¶

• Binary Trees & Binary Search Trees: definitions
• Linked tree structure and Manual construction
• Recursive binary search tree functions

## Binary Tree: def¶

• A binary tree is a structure that is either empty, or consists of a root node containing a value and references to a left and right sub-tree, which are themselves binary trees.

## Binary Search Tree (BSTree): def¶

• A binary search tree is a binary tree where the value contained in every node is:
• greater than all values in its left subtree, and
• less than all values in its right subtree

## Linked tree structure and Manual construction:¶

In [1]:
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

In [2]:
r = Node(10)
r.left = Node(5)
r.right = Node(15)
r.right.left = Node(12)
r.right.right = Node(20)

In [3]:
r.val

Out[3]:
10
In [4]:
r.right.left.val

Out[4]:
12
In [5]:
r = Node(10,
left=Node(5),
right=Node(15,
left=Node(12),
right=Node(20)))


## Recursive bstree functions¶

In [6]:
def min(t):
if t and t.left:
return min(t.left)
elif t:
return t.val

In [7]:
min(r)

Out[7]:
5
In [8]:
def max(t):
if t and t.right:
return max(t.right)
elif t:
return t.val

In [9]:
max(r)

Out[9]:
20
In [10]:
def find(t, x):
if not t:
return False
elif x < t.val:
return find(t.left, x)
elif x > t.val:
return find(t.right, x)
else: # x == t.val
return True

In [11]:
find(r, 10)

Out[11]:
True
In [12]:
find(r, 5)

Out[12]:
True
In [13]:
find(r, 14)

Out[13]:
False
In [14]:
find(r, 100)

Out[14]:
False
In [15]:
find(r, -10)

Out[15]:
False
In [16]:
def traverse(t, fn):
if t:
traverse(t.left, fn)
fn(t.val)
traverse(t.right, fn)

In [17]:
traverse(r, print)

5
10
12
15
20

In [18]:
# manually constructing an "expression tree" for 5 * (12 + 20)
r = Node('*',
left=Node(5),
right=Node('+',
left=Node(12),
right=Node(20)))

In [19]:
traverse(r, print)

5
*
12
+
20

In [20]:
def postorder_traverse(t, fn):
if t:
postorder_traverse(t.left, fn)
postorder_traverse(t.right, fn)
fn(t.val)

In [21]:
postorder_traverse(r, print) # postfix output!

5
12
20
+
*