Binary Search Trees

Trees

Terminology

• Tree - A data structure which acts as a fully connected graph without loops
• Node - May contain data, has references to children nodes
• Each node may only have a single parent, but may have 0 or more children
• Edges - Link nodes together
• Root node - Node without any parent (the start of a tree)
• Leaf node - Node without children
• Inner (or interior) node - node that is not a root node or a leaf node
• Parent node - A node that references the current node
• Child node - A node that is referenced from current node
• Descendant node - Any node (including children) which descend from current node (i.e. children, grand children, etc)
• Sibling - Nodes are siblings if they have the same parent node
• Ancestor node - Nodes that come before the current node (parent, grandparent, etc)
• Height - the maximum distance of any node from the root (if a tree only has one node (the root), the height is 0
• Depth - Distance from a given node to the root of a tree
• Level - All the nodes of a tree with the same depth

         5
        / \
       2   8
      / \   \
     1   3   15
            /  \
           13  22
          /
         12    

In the above tree can you identify:

• The root node?
• The parent of 13?
• The children of 2?
• The descendants of 8?
• The ancestors of 22?
• The interior nodes?
• The leaf nodes?
• The sibling of 3?
• The depth of 1?

Binary Trees

• Every node may only have a maximum of two children nodes (hence the term binary)
• Full tree - Every node has either 0 or 2 children (or put another way, all nodes have 2 children except for leaf nodes)
• Perfect binary tree - Binary tree in which all leaves are at the same level
• Complete binary tree, similar to full tree, but any leaf nodes must be as left as possible in the tree

Binary Search Trees

• A binary tree which keeps elements in sorted order
• Invariant: For every node, smaller values are in left subtree, larger are in right subtree (equal values are undefined and up to the implementation)
• Every insertion creates a new leaf node
• Every subtree within a BST is also a valid BST, thus a BST is a recursive structure

BST Search

• Start at root and recursively compare value we're searching for against current node
• If value is less than current node, recurse on left subtree
• If value is greater than current node, recurse on right subtree
• If recursion takes you to a leaf node, and the leaf node does not contain your value, then value is not in tree

Try it out

• Given the following tree, show the steps needed to search for the value 12

         5
        / \
       2   8
      / \   \
     1   3   15
            /  \
           13  22
          /
         12    

BST Insertions

• If tree is empty, value becomes root
• Compare value to current node starting at the root.
• If value is less than current node, recursively compare on left subbtree, otherwise if the value is greater than the current node, recursively compare on right subtree
• When recursive method attempts to recurse on left or right subtree, but that subtree is null, then new node is inserted at the position with the value

Try it out

• Create a binary search tree from the following values: 7, 4, 5, 6, 2, 9, 10, 8, 3, 1
• Create a binary search tree from the following values: 1, 2, 3, 4, 5, 6, 7

BST Removals

• Removing an item depends on three different cases

Removing a leaf node

• Simply remove the node

Removing a node with a single child

• Remove node and replace with child node

Removing a node with two children

• Remove node and replace with either in-order predecessor or in-order successor
• In-order predecessor is the left subtree's rightmost node
• In-order successor is the right subtree's leftmost node

Try it out

Using the following tree:

         5
        / \
       2   8
      / \   \
     1   3   15
            /  \
           13  22
          /
         12    

• Show what the tree looks like after removing 12
• After removing 12, show what the tree looks like after removing 22
• After removing 22, show what the tree looks like after removing 15
• Show what the tree looks like after removing the root node

In-class

• Provide recursive pseudo-code for search, add, and remove methods on a BST
• You may assume that the only thing you know about your tree is the root node
• You may assume that each node has a getLeftTree and getRightTree method
• You may assume that each node has a setLeftTree and setRightTree method