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

bst1 = Node(10)
bst1.left=Node(5)
bst1.right=Node(37)
bst1.left.right=Node(8)
bst1.right.right=Node(38)


#       10
#   5      37 
#     8        38
bst1

<__main__.Node at 0x1a84dbcfe80>

bst2 = Node(10, Node(5, None, Node(8)), Node(37, None, Node(38)))
bst2
#       10
#   5      37 
#     8        38

<__main__.Node at 0x1a84dbcfe50>

Recursive bstree functions

#  start at root
# min of a BST is the min of the left child bst (if exist), 
#or it is the value I am at if there is no left
def min(t):   # t is assumed to be a valid bst
    #initally the root
    if t and t.left:
        return min(t.left)
    elif t:
        return t.val
    else:   # on empty BST
        return None

min(bst1)
min(bst2)

5

5

def max(t):   
    if t and t.right:
        return max(t.right)
    elif t:
        return t.val
    else:   # on empty BST
        return None

max(bst1)
max(bst2)

38

38

def find(t, x):    # boolean True if found, false if not found
    # t is pointer to a node, initially the root
    if not t:  # on empty tree or if not found
        return False
    elif x==t.val:
        return True
    elif x<t.val:
        return find(t.left, x)
    else:
        return find(t.right, x)    
#       10
#   5      37 
#     8        38    

find(bst1, 10)
find(bst1, 5)
find(bst1, 8)
find(bst1, 37)
find(bst1, 38)
find(bst1, 0)
find(bst1, 99)
find(bst1, 36)

True

True

True

True

True

False

False

False

def traverse(t, fn):   # t is pointer to valid bst, fn is function to call 
    # when I visit a node
    if t:
        traverse(t.left, fn)
        fn(t.val)
        traverse(t.right,fn)
    

traverse(bst1, print)   #inorder traversal

5
8
10
37
38

def traverse1(t, fn):   # t is pointer to valid bst, fn is function to call 
    # when I visit a node
    if t:
        traverse1(t.left, fn)
        traverse1(t.right,fn)
        fn(t.val)  
         
traverse1(bst1, print)   #post order traversal
#       10
#   5      37 
#     8        38    

8
5
38
37
10

def traverse2(t, fn):   # t is pointer to valid bst, fn is function to call 
    # when I visit a node
    if t:
        fn(t.val)        
        traverse2(t.left, fn)
        traverse2(t.right,fn)
  
         
traverse2(bst1, print)   #pre order traversal
#       10
#   5      37 
#     8        38    

10
5
8
37
38

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

traverse(r, print)
traverse1(r, print)
traverse2(r, print)

5
*
12
+
20
5
12
20
+
*
*
5
+
12
20