Binary Search Tree

A Tree consists of nodes connected by edges. A binary tree is a tree in which no node can have more than two children. The two children of each node in a binary tree are called the left child and the right child. It is a finite set of nodes that can be either empty or consists of a root and two disjoint binary trees Tree Left and Tree Right called, respectively, the left and right sub-tree of the root. The left and right trees may themselves be empty; thus a node with one child could have either a left or right child.

Why to use binary tree?
As we know that searching is fast in an Ordered array and insertion and deletion is fast in linked list since we will have to change only links. Binary tree supports quick insertion and deletion as linked list and also quick searching as ordered array.

Going forward I will talk about most useful binary tree known as Binary search Tree.

What is Binary Search Tree?
A binary tree is a binary search tree if it satisfies following condition:

• All children to the left of a node have smaller values than parent.
• All children to the right of a node have larger values.

For a balanced tree [-1<= (right sub-tree height – left sub-tree height) <=1] —as the one in above Figure—the height of the tree is O(log N). However, under certain circumstances, the height of the tree can degenerate, leading to a worst-case search time of O(N) for example in left Skewed tree or right skewed tree. The height of a balanced binary with n nodes is equal to ⌊log2ⁿ⌋.

It’s very easy to understand if you know the basics of Logarithms.

In above complete binary tree we have 15 nodes which we can write as 2⁴-1.
2^h+1-1 => 2³⁺¹-1 = 15 (approximately we raised 2 to the height of the tree to get number of nodes)
When you write log2ⁿ means that how many times you will raise 2 to get n. For ex. Log2¹⁶ =4 => 2⁴=16.

The properties of binary search tree allow very efficient operations like searching, finding Minimum, Maximum, Predecessor, Successor, insertion, and deletion. The average search time for a binary search tree is directly proportional to its height: O(h). Most of the operation average case time is O(Log2ⁿ).

I will divide the BST topic in following sections:

1. Binary search tree implementation (Insert).
2. General operations on BST – search, delete, minimum, maximum, predecessor and successor.
3. BST traversal – In-Order, Pre-Order and Post-Order.
4. Balancing BST.

Binary search tree implementation (Insert)

Let us insert into a BST the following values, in the order given: 6, 4, 5, 9, 2, 7. Since the tree is initially empty, the first value, 6, becomes the new tree’s root.

The next value, 4, is less than 6, and so the 4 becomes 6’s left child.

The third value, 5, is less than 6, which means that the 5 must be placed somewhere in the root’s left subtree. Thus we move to 6’s left child is 4. Since 5 is greater than 4 and the node 4 has no right child, a new node containing 5 becomes 4’s right child.

The next value is 9 which is greater than root value and so it will go to the right subtree. Since root node doesn’t have any right child we can directly add new node containing 9 to the right of root.

The next value is 2 which is less than the root value 6 and so we will move to the left node, the left node value is 4 is greater than 2 so will move to the left of 4. Since there is no value to the left of 4, we can insert new node containing 2 to the left of 4.

The next value is 7. Start from root – 7 is greater than the root value so we will move right – right node value id 9 which is greater than 7 so move left of 9. Since there is no node to the left of 9, we can insert new node containing 7 to the left of 9.

Java implementation of Binary Search Tree

First create a node class.

public class Node {

    int value;
    Node left;
    Node right;
    Node parent;

    public Node(int value){
        this.value = value;
    }
}

Create Binary Search Tree Class and add some value to it

public class BinarySearchTree {

    Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            Node curr = root;
            Node parent = root;
            while (true) {
                parent = curr;
                if (node.value < curr.value) {
                    curr = curr.left;
                    if (curr == null) {
                        parent.left = node;
                        node.parent = parent;
                        return;
                    }

                } else if (node.value > curr.value) {
                    curr = curr.right;
                    if (curr == null) {
                        parent.right = node;
                        node.parent = parent;
                        return;
                    }
                }
            }
        }
    }
}

Inserting relatively random data usually enables the tree to maintain its O(log2^N) height, but when you insert non-random data such as a ascending/descending natural numbers or word list from a dictionary the tree will degenerate into a linked list and the height of the tree—and with it the average search time—becomes O(N). It will be either left skewed tree or right skewed tree which is not a balanced tree. There are many variations on BST which is used to balance the unbalanced tree like Red-Black Tree, AVL tree etc. (I will talk later)

Search in a Binary Search Tree

1. Start at root.
2. if root is null, the search value was not found, end the search.
3. if search-> value = root -> value then you found the value.
4. if search-> value < root -> value then follow the left subtree and go to step 2
5. if search-> value > root -> value then follow the right subtree and go to step 2

 public Node findNode(int key) {
        Node currentNode = root;
        while (currentNode.value != key) {
            if (key < currentNode.value) {
                currentNode = currentNode.left;
            } else {
                currentNode = currentNode.right;
            }

            if (currentNode == null) {
                return null;
            }
        }

        return currentNode;
    }

Minimum
The minimum of a binary search tree is the node with the smallest value. You just follow the left links to get the minimum. The minimum is the left most node in the tree.

public int findMinimum() {
        Node currentNode = root;
        while (currentNode.left != null) {
            currentNode = currentNode.left;
        }
        return currentNode.value;
    }

Maximum
The maximum is the node with the largest value. Finding the maximum is very similar to finding the minimum except that you follow the right links instead of the left. In other words, the maximum is the rightmost node in the tree.

public int findMaximum() {
        Node currentNode = root;
        while (currentNode.right != null) {
            currentNode = currentNode.right;
        }
        return currentNode.value;
    }

Go to the next page – Click on the below red circle with page number.