Binary Search Tree

In Binary Tree we need to search for an element both in left subtree and in right subtree. Due to this, the worst case complexity of search operation is O( n).

As the name suggests, the main use of this representation is for searching.

It reduces the worst case average search operation to O( logn).

Binary Search Tree Property :

In binary search trees,

• all the left subtree elements should be less than root data and 
• all the right subtree elements should be greater than root data. 

This is called binary search tree property.

Binary Search Tree Declaration

Operations on Binary Search Trees

Main operations: 

Following are the main operations that are supported by binary search trees: Binary Search Tree ADT

• Find/ Find Minimum / Find Maximum element in binary search trees 
• Inserting an element in binary search trees 
• Deleting an element from binary search trees 

Auxiliary operations: 

Checking whether the given tree is a binary search tree or not 

• Finding kth-smallest element in tree 
• Sorting the elements of binary search tree and many more

Important Notes on Binary Search Trees

• InOrder Traversal produces sorted list. For above example: InOrder Traversal = 2,4,5,7,9 (sorted)
• Binary search trees consider either left or right subtrees for searching an element but not both.
• Basic operations in BST runs in O(logn) worst case time. if tree is linear chain of n nodes(like skew tree) then worst case time is O(n).

Finding An Element in BST

If the data we are searching is less than nodes data then search left subtree of current node; otherwise search right subtree of current node.

• Recursive 
• Non-Recursive 

Problems:

• Problem1 : Given pointers to two nodes, find Lowest Common Ancestor(LCA)

                                                     The LCA od 6 and 1 is 8.
           - See Link

• Problem2 : Give an algorithm for counting the number of BSTs possible with n nodes - See Link
• Problem3 : Give an algorithm to check whether the given binary tree is a BST or not. - See Link