Binary Search Trees

Agenda

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

# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"

# tree (1 to N) data structure - every node can be connected to multiple other nodes, but there is a unique path
# between any two nodes (no loops)   if loops are allowed then it is a graph (N to N)

Rooted 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.

Rooted Binary Search Tree (BSTree): def

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

Linked tree structure and Manual construction:

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

root = Node(37)
root.val
root.left
root.right

37

root.right=Node(54)

root.right
root.right.val
root.right.left
root.right.right

<__main__.Node at 0x1cef6e30a60>

54

root.left=Node(12,Node(3), Node(30))
      #        37
      #    12      54
      #  3   30

Recursive bstree functions

def min(t):  # from root, go left as far as you can, return that value
    if t:
        temp=t
        while temp.left:
            temp=temp.left
        return temp.val
    else:
        return None

min(root)

3

min(root.right)

54

min(root.right.right)

def min_rec(t):  # from root, go left as far as you can, return that value
# min of a tree is the min of tree.left (if exist)
# base case, if no left child, return the value at this node
    if t and t.left:
        return min_rec(t.left)
    elif t:   # but no left child
        return t.val   # t must be the leftmost child, the min
    else:
        return None

min_rec(root)
min_rec(root.right)
min_rec(root.right.right)

3

54

def max_rec(t):  # from root, go right as far as you can, return that value
    if t and t.right:
        return max_rec(t.right)
    elif t:   
        return t.val   
    else:
        return None

max_rec(root)
max_rec(root.left)

54

30

# runtime growth of min or max is O(N)  N being the number of nodes in the rooted binary tree
# we cannot guarantee the balance of the tree
# O(height of tree)    height of tree is between lgN and N

def find(t, x):   # returns True or False   t is root to a BST, x is value to look for
    if not t:
        return False
    elif t.val==x:
        return True
    elif t.val<x:
        return find(t.right, x)
    else:
        return find(t.left, x)
    # O(height of the tree)   height of tree is bewteen N and lgN

      #        37
      #    12      54
      #  3   30

find(root, 34)
find(root, 37)
find(root, 3)
find(root, 54)
find(root, 100)

False

True

True

True

False

def traverse(t, fn):   # itertor, makes sense to iterate in sorted order
    # traverse tree by first traversing tree.left entirly, then tree.val, then traverse tree.right entirly
  # base case, if t is None, do nothing
        # traverse(t.left, fn)
        # fn(t.val)
        # traverse(t.right fn)
    if t:
        traverse(t.left, fn)
        fn(t.val)
        traverse(t.right, fn)

traverse(root, print)

3
12
30
37
54

r = Node('*', 
         left=Node(5), 
         right=Node('+', 
                    left=Node(12),
                    right=Node(20)))
# expression tree, not a binary search tree
#                 *
#           5             +
#                     12      20
#5*(12+20)

traverse(r, print)

5
*
12
+
20

def preorder_traverse(t, fn):   # itertor, makes sense to iterate in sorted order
    # traverse tree by first traversing tree.left entirly, then tree.val, then traverse tree.right entirly
  # base case, if t is None, do nothing
        # traverse(t.left, fn)
        # fn(t.val)
        # traverse(t.right fn)
    if t:
        fn(t.val)
        preorder_traverse(t.left, fn)
        preorder_traverse(t.right, fn)

preorder_traverse(r, print)
# * 5 + 12 20

*
5
+
12
20