Binary Search Tree - 2

Traversing the Tree

• Traversing a tree means visiting each node in a specified order.
• There are three simple ways to traverse a tree.
  • preorder
  • inorder
  • postorder

Inorder Traversal :

• The method needs to do only three things :

  1. Call itself to traverse the node’s left subtree.
  2. Visit the node.
  3. Call itself to traverse the node’s right subtree.

• Implement inorder traversal by recursion.

		
//pseudo code
public static void main(String args[]) { 
    inOrder(root); 
} 
	    
private void inOrder(Node localRoot) {
    if(localRoot != null) {
		    
        inOrder(localRoot.leftChild);
			    
        System.out.print(localRoot.iData + “ “);
			    
        inOrder(localRoot.rightChild);
    }
    }

Example :

Preorder Traversal :

• The method needs to do only three things :
  1. Visit the node.
  2. Call itself to traverse the node’s left subtree.
  3. Call itself to traverse the node’s right subtree.

Postorder Traversal :

• The method needs to do only three things :
  1. Call itself to traverse the node’s left subtree.
  2. Call itself to traverse the node’s right subtree.
  3. Visit the node.

Inorder V.S. Preorder V.S. Postorder Traversal :

Example : algebraic expression :

Finding Maximum and Minimum Values in Binary Search Tree :

• For the minimum, go to the left child of the root; then go to the left child of that child, and so on, until you come to a node that has no left child. This node is the minimum.

• For the maximum value in the tree, follow the same procedure, but go from right child to right child until you find a node with no right child. This node is the maximum.

 //pseudo code
// returns node with minimum key value
public Node minimum() {
    Node current, last;
    current = root; // start at root

    // until the bottom,
    while(current != null) {
        last = current; // remember node
        current = current.leftChild; // go to left child
    }
     
    return last;
}

Deleting a Node :

• Deleting a node is the most complicated common operation required for binary search trees.
• There are three cases to consider:
  1. The node to be deleted is a leaf (has no children).
  2. The node to be deleted has one child.
  3. The node to be deleted has two children.

Case 1: The Node to Be Deleted Has No Children :

• To delete a leaf node, you simply change the appropriate child field in the node’s parent to point to null, instead of to the node.
• The node will still exist, but it will no longer be part of the tree.

//pseudo code
// delete node with given key
public boolean delete(int key) {
    // (assumes non-empty list)
    Node current = root;
    Node parent = root;
    boolean isLeftChild = true;

    // search for node
    while(current.iData != key) {
        parent = current;
		
        // go left?
        if(key < current.iData) {
            isLeftChild = true;
            current = current.leftChild;
        } else {
            // or go right?
            isLeftChild = false;
            current = current.rightChild;
        }

        // end of the line,
        if(current == null) {
            // didn’t find it
            return false;
        }
		
        //delete node
        // if no children, simply delete it
        if(current.leftChild == null && current.rightChild == null) {
            // if root,
			   if(current == root) {
			       root = null; // tree is empty
			   } else if(isLeftChild) {
			   // disconnect from parent
			   parent.leftChild = null;
			   } else {
			       parent.rightChild = null;
			   }
			
        }
    }
}

Case 2: The Node to Be Deleted Has One Child :

• The node has only two connections: to its parent and to its only child.
• You want to “snip” the node out of this sequence by connecting its parent directly to its child.
• This process involves changing the appropriate reference in the parent (leftChild or rightChild) to point to the deleted node’s child.

//pseudo code
//delete node

// if no right child, replace with left subtree
else if(current.rightChild==null) {
    if(current == root) {
        root = current.leftChild;
    } else if(isLeftChild) {
        // left child of parent
        parent.leftChild = current.leftChild;
    } else {
        // right child of parent
        parent.rightChild = current.leftChild;
    }
}

// if no left child, replace with right subtree
else if(current.leftChild==null) {
    if(current == root) {
        root = current.rightChild;
    } else if(isLeftChild) {
        // left child of parent
        parent.leftChild = current.rightChild;
    } else {
        // right child of parent
        parent.rightChild = current.rightChild;
    }
}

Case 3: The Node to Be Deleted Has Two Children :

• If the deleted node has two children, you can’t just replace it with one of these children, at least if the child has its own children.
• For each node, the node with the next-highest key is called its inorder successor, or simply its successor.
• To delete a node with two children, replace the node with its inorder successor.

Finding the Successor :

• What we’re really looking for is the smallest of the set of nodes that are larger than the original node.
• When you go to the original node’s right child, all the nodes in the resulting subtree are greater than the original node because this is how a binary search tree is defined.
• Now we want the smallest value in this subtree. As we learned, you can find the minimum value in a subtree by following the path down all the left children.

Trees Represented as Arrays :

• With this scheme, a node’s children and parent can be found by applying some simple arithmetic to the node’s index number in the array.
• If a node’s index number is index :
  • this node’s left child is : 2*index + 1
  • its right child is : 2*index + 2
  • its parent is : (index-1) / 2