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"

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

myTree = Node(10)
myTree.left=Node(5)
myTree.right=Node(15)
myTree.right.left=Node(12)
myTree.right.right=Node(20)

#                  10
#              5       15
#                    12   20
# myTree is a pointer to the root

Recursive bstree functions

def min(t):
    # go left as far as possible, return the value when that node has no more left
    if t.left:
        return min(t.left)
    return t.val

min(myTree)

5

min(myTree.right)

12

min(myTree.left)

5

def max(t):
    if t.right:
        return max(t.right)
    return t.val

max(myTree)
max(myTree.right)
max(myTree.left)

20

20

5

def find(t, x):  # intial call t is root of BST
    # compare x to t.val, if == then DONE(true), or if x<t.val RECURSE ON LEFT  else if x>t.val RECURSE RIGHT
    # to base cases, t.val==x  TRUE   or t is None   FALSE
    if not t:
        return False
    elif t.val==x:
        return True
    elif t.val>x:
        return find(t.left,x)
    else:
        return find(t.right,x)
    
find(myTree, 10)
find(myTree, 7)

True

False

def traverse(t, fn):   
    # pass it the root of a BST, and a function to apply at each node in traversal order  INORDER
    if not t:
        pass
    else:
        traverse(t.left, fn)
        fn(t.val)
        traverse(t.right, fn)
traverse(myTree, print)
#INORDER visit a node between its children trees

5
10
12
15
20

def rev_traverse(t, fn):   
    if not t:
        pass
    else:
        rev_traverse(t.right, fn)
        fn(t.val)
        rev_traverse(t.left, fn)

rev_traverse(myTree, print)

20
15
12
10
5

def traverse1(t, fn):   
    # pass it the root of a BST, and a function to apply at each node in traversal order  INORDER
    if not t:
        pass
    else:
        fn(t.val)
        traverse1(t.left, fn)
        traverse1(t.right, fn)
traverse1(myTree, print)
#                  10
#              5       15
#                    12   20
# myTree is a pointer to the root
#PRE-ORDER traversal, visit a node before both its children

10
5
15
12
20

def traverse2(t, fn):   
    # pass it the root of a BST, and a function to apply at each node in traversal order  INORDER
    if not t:
        pass
    else:
        traverse2(t.left, fn)
        traverse2(t.right, fn)
        fn(t.val)        
traverse2(myTree, print)
#                  10
#              5       15
#                    12   20
# myTree is a pointer to the root
#POST-ORDER traversal, visit a node after both its children

5
12
20
15
10