Introduction to Binary Search Tree Data Structure

A binary search tree is a special variant and most commonly used form of binary tree. A binary search tree is made of nodes where each node has at most 2 references, a "left" reference and a "right" reference and a data element. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree. (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.

Why to use binary search tree:

  • The inorder traversal of the tree, returns a sorted list of the tree. This is helpful to return data in sorted manner.
  • Searching an element, if present takes O(h), where h is the height of the tree.

Operations on Binary Search Tree

  • Insertion: Traverse the tree from the root and traverse left if the new node value is less that root or traverse right if it higher. Perform this step recursively, until a leaf node is reached. Add it to the leaf node, satisfying the property.
  • Search: Traverse the tree from the root and traverse left if the new node value is less that root or traverse right if it higher. Perform this step recursively, until the node with the value is found
  • Deletion: Deletion is tricky, since it has couple of various cases. To do the deletion, first start from the root and find the node.

Deleting a node that does not have a leaf root (13) -: Just remove the node. 

       (8)                      (8)     
      /   \                    /   \    
   (2)     (21)             (2)     (21)
  /   \     /     ===>     /   \   
(1)   (5) (13)           (1)   (5)

Deleting a node which has a child (21) -: remove the node and move its child up

        (8)                      (8)     
      /   \                    /   \    
   (2)     (21)             (2)     (13)
  /   \     /     ===>     /   \   
(1)   (5) (13)           (1)   (5)

Deleting a node which has two child (2) -: remove the node (2) and swap the node with one of the following:

  • The largest node on the left side
  • Smallest node on the right side

        (8)                      (8)     
      /   \                    /   \    
   (2)     (21)             (2)     (13)
  /   \     /     ===>     /   \   
(1)   (5) (13)           (1)   (5)

I will be posting the code for operations soon