Binary Search Tree

A Binary Search Tree(BST) is a node-based binary tree data structure which has the following properties:
1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

One major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Example


Terms Used In BST
1. Node: An item that is stored in the tree.
2. Root: The top item in the tree (50 in above case)
3. Child: Node(s) under the current node.
4. Parent: The node that is present directly above the current node. (90 is the parent of 100 in above case).
5. Leaf : A node which has no children(20 is a leaf in the above case)

Searching in a BST
1. Start at the root node.
2. If the item that you are searching for is less than the root node, move to the left child of the root node, else if the item that you are searching for is more than the root node, move to the right child of the root node and if it is equal to the root node, then you have found the item that you are looking for :)
3. Now check to see if the item that you are searching for is equal to, less than or more than the new node that you are on. Again perform step 2.
4. Repeat this process until you find the item that you are looking for or until the node doesn't have a child on the correct branch, in which case the tree doesn't contain the item which you are looking for.

Code Example

bool BinarySearchTree::search(int val)
{
    Node *next = this->root();
    while (next != NULL) {
        if (val == next->value()) {
            return true;
        } else if (val < next->value()) {
            next = next->left();
        } else {
            next = next->right();
    }
}
    //Element not found
    return false;
}

Complexity
Average Case:
If we have a tree with n nodes, then with each step we halves the value n. So the number of steps the algorithm takes equals the number of times we can halve n. By definition, this is exactly log n. So the algorithm is of O(log n)

Best case : O(1)
Worst case: O(n)

Other Operations:
The other operations that are performed on a BST are:
1. Adding an item to a binary search tree (coming soon)
2. Deleting an item from a binary search tree (coming soon)

Binary Tree and It's Traversal

A tree is called a binary tree where each node has zero, one, or two children ie. at most 2 children.

There are three different methods for traversing binary trees: preorder, postorder and in-order.

Preorder
preorder: Current node, left subtree, right subtree

preorder(node)
    visit(node)
    if node.left != null then preorder(node.left)
    if node.right != null then preorder(node.right)

Postorder
postorder: Left subtree, right subtree, current node

postorder(node)
    if node.left != null then postorder(node.left)
    if node.right != null then postorder(node.right)
    visit(node)

Inorder
in-order: Left subtree, current node, right subtree

inorder(node)
    if node.left != null then inorder(node.left)
    visit(node)
    if node.right != null then inorder(node.right)

Example

If we have a tree as shown above, then the output for different traversal method will be as:
1. preorder : 50, 30, 20, 40, 90, 100
2. postorder : 20, 40, 30, 100, 90, 50
3. inorder : 20, 30, 40, 50, 90, 100