Binary Search Tree

Definition

A binary tree where:

• The values in the nodes in the left subtree of the node x in the tree has a smaller value than x

• The values in the nodes in the right subtree of the node x in the tree has a greater value than x

Based on this definition, we can get the most important feature of BST: The inorder traversal of BST results in an ascending sequence.

For example:

The inorder traverse of the tree is [ 1 2 3 4 6 7 9].

LintCode Problem: Valid Binary Search Tree.

Search

The search procedure of BST is similar to binary search.
Usually the problem will give a value or a node.

• Start from the root
• If TreeNode.val > value, go to right subtree
• If TreeNode.val < value, go to left subtree

NOTICE: Never modify the root. Start by declare a new tree node and refer to the root!!!

LintCode Problem:Search Range in Binary Search Tree

Analysis: 3 situation: 1.==; 2.>; 3.< .

Implementation: Find Node in Java

Public TreeNode parent; // Create reference for parent node
/** Find node with given value in BST
  * @param root of the binary search tree
  * @param the value to search
  * @return the reference to the target node, or null if not found
 */
public TreeNode findNode(TreeNode root, int value){
        TreeNode prev = root;
        TreeNode current = root;

        while(current != null){
            if (current.val == val){
                parent = prev;
                return current;
            }
            if (current.val > value){
                prev = current;
                current = current.left;
            }
            else{
                prev = current;
                current = current.right;
            }
        }

        parent = prev;  // Assign global variable parent
        return null;
    }

Insert Node

Insert node into an existing binary search tree is easy.

All we need to do is just find the parent node of the target position, then add the node to parent's left or parent's right.**

LintCode Problem: Insert Node in a Binary Search Tree

After finding the parent node, we can just reside the node based on its value comparing with parent.val.

We can use the previous method findNode() to set the parent node.
Or we can also implement a new method to return the parent node reference.

/** Find parent node with given value in BST
  * @param root of the binary search tree
  * @param the value to search
  * @return the reference to the parent node
 */
public TreeNode findParent(TreeNode root, int value){
        TreeNode prev = root;
        TreeNode current = root;

        while(current != null){
            if (current.val > value){
                prev = current;
                current = current.left;
            }
            else{
                prev = current;
                current = current.right;
            }
        }

        return prev;
    }

Delete Node

Removing a Node from existing Binary Search Tree has three situations:

1. Remove a node has no child.

   In this situation, we can directly remove the node.
   
   The corresponding code is showing below:

   {
      TreeNode parent;
      TreeNode del;
      if (del.right == null && del.left == null){
          if (parent.left == del)
              parent.left = null;
          else
              parent.right = null;
      }
   }
   

2. Remove a node has only on child.

   In this situation, we can splice the child of removed node to its parent.
   
   The corresponding code is showing below:

   {
        TreeNode paren;
        TreeNode del;
        if (del.right == null || del.left == null){
            if (parent.right == del){
                if (del.right == null)
                    parent.right = del.left;
                else
                    parent.right = del.right;
            }
            else{
                if (del.right == null)
                    parent.left = del.left;
                else
                    parent.lwft = del.right;
            }
        }
   }
   

3. Remove a node has two children.

   This is the most tricky situation. But not hard to handle.

   All we need to do is to replace the removed node with the least value in its right subtree.

   This replacement will not break the BST properties: Cause all the nodes in its right subtree have greater value than the node. So we just choose the least greater value.
   
   The corresponding code is showing below:

        TreeNode replace;
        TreeNode temp = del;
        TreeNode temp_parent = del;
        while (temp.left != null){
            temp_parent = temp;
            temp = temp.left;
        }
        del.val = temp.val;
        // Just as remove leaf node above
        remove(temp, temp_parent);

Lintcode Problem: Remove Node in Binary Search Tree
Notice: Need to consider the situation when the removed node is the root.

Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

• Elements are visited in ascending order (i.e. an in-order traversal)

• next() and hasNext() queries run in O(1) time in average.

Analysis: This problem can use the same method as non-recursion inorder traversal.

public class BSTIterator {
    // Member
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    private TreeNode curr;

    //@param root: The root of binary tree.
    public BSTIterator(TreeNode root) {
        curr = root;
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        // write your code here
        return (curr != null || !stack.empty());
    }

    //@return: return next node
    public TreeNode next() {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }

        curr = stack.pop();
        TreeNode node = curr;
        curr = curr.right;

        return node;
    }
}