Trees

class BinaryTreeNode:
    def __init__(self, key=None, left=None, right=None, p=None):
        self.key = key
        self.left = left
        self.right = right
        self.p = p

class BinarySearchTree:
    def __init__(self, root=None):
        self.root = root

Binary Search Tree

A binary search tree node consists of:

1. \(key: \;\) value of the node
2. \(left: \;\) left children
3. \(right: \;\) right children
4. \(p: \;\) parent

If a child or the parent is missing, the appropriate attribute contains the value None. The root node is the only node in the tree whose parent is None.

The keys in a binary search tree are always stored in such a way as to satisfy the binary search tree property:

For any node \(x\), the keys in the left subtree of \(x\) are at most \(x.key\), and the keys in the right subtree of \(x\) are at least \(x.key\).

The binary search tree property allows us to print out all the keys in a binary search tree in sorted order by inorder tree walk (Inorder traversal). This algorithm prints the key of the root of a subtree betweeen printing the values in its left subtree and printing those in its right subtree. Similarly, a preorder tree walk prints the root before the values in either subtree and a postorder tree walk prints the root after the values in its subtrees.

Inorder Traversal

def inorder_tree_walk(tree):

    def inorder(root):
        if not root:
            return
        
        inorder(root.left)
        print(root.val)
        inorder(root.right)
        
    inorder(tree)

Preorder Traversal

def preorder_tree_walk(tree):

    def preorder(root):
        if not root:
            return
        
        print(root.val)
        preorder(root.left)
        preorder(root.right)
        
    preorder(tree)

Postorder Traversal

def postorder_tree_walk(tree):

    def postorder(root):
        if not root:
            return
        
        postorder(root.left)
        postorder(root.right)
        print(root.val)
        
    postorder(tree)

Search

We use the following procedure to search for a node with a given key in a binary search tree. Given a pointer to the root of the tree and a key \(k\), it returns a pointer to a node with key \(k\) if one exists, otherwise it returns None.

def tree_search(tree, k):
    
    def search(root, val):
        # base case
        if not root or root.key == val:
            return root
        
        if root.key < val:
            target = search(root.right, val)
        else:
            target = search(root.left, val)
        
        return target
    
    return search(tree, k)

Minimum

We can always find an element in a binary search tree whose key is a minimum by following \(left\) child pointers from the root until we encounter a None. The following procedure returns a pointer to the minimum element in the subtree rooted at a given node \(x\):

def tree_minimum(tree):
    
    def minimum(root):
        # base case
        if not root.left:
            return root
        
        return minimum(root.left)
    
    return minimum(tree)

Maximum

The maximum is symmetric as minimum:

def tree_maximum(tree):
    
    def maximum(root):
        # base case
        if not root.right:
            return root
        
        return maximum(root.right)
    
    return maximum(tree)

Successor and Predecessor

Given a node in a binary search tree, sometimes we need to find its successor in the sorted order determined by an inorder tree walk. If all keys are distinct, the successor of a node \(x\) is the node with the smallest key greater than \(x.key\). The procedure breaks into several cases:

1. If node \(x\) has right subtree, then the successor must be the smallest element in the right subtree.
2. If node \(x\) does not have right subtree and itself is a leftsubtree of its parent, then the successor must be its parent.
3. If node \(x\) does not have right subtree and itself is a rightsubtree of its parent, then the successor must be the lowest ancestor of \(x\) whose left child is also an ancestor of \(x\).

def tree_successor(node):
    # case 1
    if node.right:
        return tree_minimum(node)
    
    # case 2, 3
    curr_p = node.p
    while curr_p:
        if curr_p.left == node:
            return curr_p
        
        node = curr_p
        curr_p = node.p
        
    return None

Predecessor is symmetric

Insertion

To insert a new node \(z\) into a binary search tree \(T\) we use the following procedure:

1. Begin at root of the tree, we maintain two pointers \(y, x\) representing parent and current node respectively.
2. Go down the tree and compare every node encounter with \(z\), if it is greater than \(z\) we go to the left, if smaller we go to the right, until we reach None.
3. We replace \(y.left\) or \(y.right\) with \(x\) and fill \(z.p = y\).

def tree_insert(T, z):
    # initialize y, x representing parent and current node
    y, x = None, T
    # step 2
    while x:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    
    # step 3
    z.p = y
    # if tree is empty
    if not y:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

Deletion

The overall strategy for deleting a node \(z\) from a binary search tree \(T\) has three basic cases:

1. If \(z\) has no children, then we can simply remove it by modifying its parent to replace \(z\) with None as its child.
2. If \(z\) has just on child, then we elevate that child to take \(z\)'s position in the tree by modifying \(z\)'s parent to replace \(z\) by \(z\)'s child.
3. If \(z\) has two children, then we find \(z\)'s successor \(y\) which must be the minimum item in \(z\)'s right subtree (with no left child). Now have two cases:
   1. If \(y\) is \(z\)'s right child: We replace \(z\) by \(y\) and \(z\)'s left child becomes \(y\)'s left child.
   2. If \(y\) is not \(z\)'s right child: We first replace \(y\) by its right child, then we replace \(z\) by \(y\)

In order to move subtrees around, we define a helper function transplant that replaces the subtree rooted at node \(u\) with the subtree rooted at node \(v\).

def transplant(T, u, v):
    # if u is the root
    if not u.p:
        T.root = v
    elif u.p.left == u:
        u.p.left = v
    else:
        u.p.right = v

    # replace v with u
    if v:
        v.p = u.p

def tree_delete(T, z):
    # case 1
    if not z.left and not z.right:
        transplant(T, z, None)
    # case 2
    elif not z.left and z.right:
        transplant(T, z, z.right)
    elif not z.right and z.left:
        transplant(T, z, z.left)
    else:
        y = tree_successor(z)
        # case 3.2
        if z.right != y:
            transplant(T, y, y.right)
            y.right = z.right
            y.right.p = y
            
        transplant(T, z, y)
        y.left = z.left
        y.left.p = y
    

Complexcity

• Tree walks: \(\; \Theta(n)\)
• Search, Minimum, Maximum, Successor, Predecessor, Insert, Delete: \(\; O(h)\)