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
+
*