Binary Tree Operations

last updated 3/28/07

 


Traversals of Binary Trees

Common parent-child traversals

Inorder: visit left subtree, visit root, visit right subtree  Preorder: visit root, visit left, visit right  Postorder: visit left, visit right, visit root 
private void Inorder(BSTNode root) 
{ 
  if(root != null) { 
    Inorder(root.left);
    Process(root.value);
    Inorder(root.right);
  } 
}

public void Inorder(){
    Inorder(root);
}

private void Preorder(BSTNode root) 
{ 
  if(root != null) {
    Process(root.value);
    Preorder(root.left);
    Preorder(root.right);
  } 
}

public void Preorder(){
    Preorder(root);
}

private void Postorder(BTSNode root)
{ 
  if(root != null) {
    Postorder(root.left);
    Postorder(root.right);

    Process(root.value); 
  } 
}

public void Postorder(){
    Postorder(root);
}

Level order traversal: starting with the root, process all nodes at each level left to right before proceeding to the next level. What data structure will you need to accomplish this?

 

 

 


Examples of Traversals

Deletion of an entire tree (post order traversal)

void DeleteAll(BSTNode cur)
{
    if(cur != NULL) {
        DeleteAll(cur.getLeft());
        DeleteAll(cur.getRight());
        cur = null; //now delete node
    }
}

Why wouldn't we want to do a preorder traversal for deletion?

 

 

 

 


Implementation of isEmpty and isFull

 

  public boolean isEmpty()
  // Determines whether this BST is empty
  {
    return (root == null);
  }

  public boolean isFull()
  // Determines whether this BST is full
  {
    return false;
  }

 

 


Number of Nodes

Note difference in code complexity for recursive and nonrecursive solutions.  Of course if we tracked the number of nodes through insertion and deletion operations, this routine would trivially return the count.

  private int recSize(BSTNode tree)
  // Determines the number of nodes in tree recursively
  {
    if (tree == null)    
      return 0;
    else
      return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
  }

  public int Size()
  // Determines the number of nodes in this BST
  {
    return recSize(root);
  }

  public int Size2()
  // Determines the number of nodes in this BST non-recursively  {
    int count = 0;
    if (root != null)
    {
      LinkedStack hold = new LinkedStack();
      BSTNode currNode;
      hold.push(root);
      while (!hold.isEmpty())
      {
        currNode = (BSTNode) hold.top();
        hold.pop();
        count++;
        if (currNode.getLeft() != null)
          hold.push(currNode.getLeft());
        if (currNode.getRight() != null)
          hold.push(currNode.getRight());
      }
    }
    return count;
  }

 


contains and get Implementation

  private boolean recContains(Comparable item, BSTNode tree)
  // returns true if item is in tree, false otherwise
  {
    if (tree == null)
      return false;                      // item is not found
    else if (item.compareTo(tree.getInfo()) < 0)
      return recIsThere(item, tree.getLeft());  // Search left subtree
    else if (item.compareTo(tree.getInfo()) > 0)
      return recIsThere(item, tree.getRight()); // Search right subtree
    else
      return true;                         // item is found
  }

  public boolean contains (Comparable item)
  // Determines if element matching item is in this BST.
  {
    return reContains(item, root);
  }
  
  private Comparable recGet(Comparable item, BSTNode tree)
  // Returns the element in tree with the same key as item.
// Pre: isThere(item)==true
{ if (item.compareTo(tree.getInfo()) < 0) return recRetrieve(item, tree.getLeft()); // retrieve from left subtree else if (item.compareTo(tree.getInfo()) > 0) return recRetrieve(item, tree.getRight()); // retrieve from right subtree else return tree.getInfo(); } public Comparable get(Comparable item) // Returns the BST element with the same key as item.
// Pre: isThere(item)==true
{ return recGet(item, root); }


Non-recursive contains and get Implementation

These two operations can be expressed as non-recursive routines.

  public boolean contains (Comparable item)
  // Determines if element matching item is in this BST.
  {
    BSTNode temp = root;
    while(temp != null){
        int comp = item.compareTo(temp.getInfo());
        if(comp==0)
            return true;
        else if (comp<0)
            temp = temp.getLeft();
        else
            temp = temp.getRight();
     }
     return false;
   }

  public Comparable get(Comparable item)
  // Returns the BST element with the same key as item.
// Pre: isThere(item)==true
{ BSTNode temp = root; while(temp != null){ int comp = item.compareTo(temp.getInfo()); if(comp==0) return temp.getInfo(); else if (comp<0) temp = temp.getLeft(); else temp = temp.getRight(); } return null; }


Insertion

  private BSTNode recAdd(Comparable item, BSTNode tree)
  // Inserts item into the tree
  {
    if (tree == null)
    {// Insertion place found
      tree = new BSTNode(item);
    }
    else if (item.compareTo(tree.getInfo()) <= 0)
      tree.setLeft(recAdd(item, tree.getLeft()));  // Insert in left subtree
    else
      tree.setRight(recAdd(item, tree.right()));   // Insert in right subtree
    return tree;
  }

  public void insert (Comparable item)
  // Adds item to this BST.
  {
    root = recAdd(item, root);
  }

Insertion order has an effect on the tree structure



Removal

Three cases:






Removal Code

    private BSTNode removeNode(BSTNode tree)
  // Deletes the node referenced by tree
  // Post: The user's data in the node referenced to by tree is no
  //       longer in the tree.  If tree is a leaf node or has only
  //       a non-null child pointer, the node pointed to by tree is
  //       deleted; otherwise, the user's data is replaced by its
  //       logical predecessor and the predecessor's node is deleted
  {
    Comparable data;

    if (tree.getLeft() == null)
      return tree.getRight();
    else if (tree.getRight() == null) 
      return tree.getLeft();
    else
    {
      data = getPredecessor(tree.getLeft());
      tree.setInfo(data);
      tree.setLeft(recDelete(data, tree.getLeft()));  // Delete predecessor node
      return tree;
    }
  }
  private Comparable getPredecessor(BSTNode tree)
  // Returns the info member of the rightmost node n tree
  {
     while (tree.getRight() != null)
         tree = tree.getRight();
     return tree.getInfo();
  }
   private BSTNode recRemove(Comparable item, BSTNode tree)
  // Deletes item from the tree
  {
    if(tree==null)
      found = false;
    else if (item.compareTo(tree.getInfo()) < 0)
      tree.setLeft(recRemove(item, tree.getLeft()));
    else if (item.compareTo(tree.getInfo()) > 0)
      tree.setRight(recRemove(item, tree.getRight()));
    else {
      tree = removeNode(tree);
      found = true;
    }
    return tree;
  }

  public boolean remove (Comparable item)
  // Delete the element of this BST whose key matches itemís key.
  {
    root = recDelete(item, root);
    return found;
  }

 


reset and getNext operations

 public int reset(int orderType)
  // Initializes current position for an iteration through this BST in orderType order
  {
    int numNodes = numberOfNodes();
    if (orderType == INORDER)
    {
      inOrderQueue = new ArrayQueue(numNodes);
      inOrder(root);
    }
    else
    if (orderType == PREORDER)
    {
      preOrderQueue = new ArrayQueue(numNodes);
      preOrder(root);
    }
    if (orderType == POSTORDER)
    {
      postOrderQueue = new ArrayQueue(numNodes);
      postOrder(root);
    }
    return numNodes;
  }

  public Comparable getNextItem (int orderType)
  // Returns a copy of the element at the current position in this BST and advances 
  // the value of the current position based on the orderType set through reset
  {
    if (orderType == INORDER)
      return (Comparable)inOrderQueue.dequeue();
    else if (orderType == PREORDER)
      return (Comparable)preOrderQueue.dequeue();
    else if (orderType == POSTORDER)
      return (Comparable)postOrderQueue.dequeue();
    else return null;
  }

    private void inOrder(BSTNode tree)
  // initializes inOrderQueue with tree elements in inOrder order
  {
    if (tree != null)
    {
      inOrder(tree.left);
      inOrderQueue.enqueue(tree.getInfo());
      inOrder(tree.right);
    }
  }

  private void preOrder(BSTNode tree)
  // initializes preOrderQueue with tree elements in preOrder order
  {
    if (tree != null)
    {
      preOrderQueue.enqueue(tree.getInfo());
      preOrder(tree.left);
      preOrder(tree.right);
    }
  }

  private void postOrder(BSTNode tree)
  // initializes postOrderQueue with tree elements in postOrder order
  {
    if (tree != null)
    {
      postOrder(tree.left);
      postOrder(tree.right);
      postOrderQueue.enqueue(tree.getInfo());
    }
  }


Collection Operations: Big-O

Comparison of BST and Linear Lists
Operation BST Array List Linked List
Class constructor
O(1)
O(1)
O(1)
isFull
O(1)
O(1)
O(1)
isEmpty
O(1)
O(1)
O(1)
reset
O(N)
O(1)
O(1)
getNextItem
O(1)
O(1)
O(1)
isThere
O(log N)
O(log N)
O(N)
retrieve (find
+process
=total
O(log N)
+O(1)
=O(log N)
O(log N)
+O(1)
=O(log N)
O(N)
+O(1)
=O(N)
insert (find
+process
=total
O(log N)
+O(1)
=O(log N)
O(log N)
+O(N)
=O(N)
O(N)
+O(1)
=O(N)
delete (find
+process
=total
O(log N)
+O(1)
=O(log N)
O(log N)
+O(N)
=O(N)
O(N)
+O(1)
=O(N)

 


Final Remarks

The BST in the above analysis is assumed to be rather balanced.  Algorithms are studied in A&A to ensure that a tree is maintained in a balanced state.  These algorithms do not affect the complexity cost, i.e., they remain logarithmic.

A variation on the BST is a B-tree (the "B" is for the creator, Bayer) which shortens the height of the tree for even faster operations.  B-trees are balanced by definition and are one of the popular data structures for use in a database.