Home » Data Structure

Introduction to Binary Search Tree (BST)

In this article, we are going to see what is binary search tree and why do we require it and what are properties of a binary tree?
Submitted by Radib Kar, on September 16, 2020

We already know that Binary search Tree is a special kind of Binary Tree which is a very efficient data structure for searching. In Normal binary trees, the parent has no relationship with the child in terms of values, or say there is no restriction on nodes data. That's why while searching an element in a normal Binary Tree, we need to search the entire tree or say, the search is not at all guided resulting in the Time complexity of O(n).

There comes the need of a Binary Search Tree. A tree is a hierarchical data structure and we expect the time complexity of the ADT operations to be concerning the tree height, not concerning tree size. In the case of Binary search tree, there is a restriction in the node data population which results in a better searching time complexity, on average O(log N) or O(h) where h be the tree height.

Binary Search Tree Property

1. All node values must be distinct
2. Parent value must be greater than the left child value and smaller than the right child value
3. Both the left and right subtree needs to be Binary search tree as well
4. All the node in the left subtree of the root has less key/node value than the root
5. All the node in the right subtree of the root has greater key/node value than the root

Examples:

1. BST:
   Below is the example of a BST as it maintains all the properties.
   
   
2. Not a BST:
   Below is the example which is not a BST as the left subtree (rooted by 6) is not a BST here.
   
   

ADT operation on Binary Search Trees:

1. Insert a Node (Insertion in a Binary Search Tree)
2. Delete a Node (Deletion in Binary Search Tree)
3. Search a Node
4. Find Minimum node value
5. Find Maximum node value

Few More Interesting Points/Properties

1. Inorder traversal of the binary search trees produces a sorted list since all node in the left subtree of the root is smaller than root and all nodes in the right subtree of the root are greater than the root.
2. Searching doesn't require to search the whole tree as we can search only in one subtree depending on search value. If the search value is greater than root value then search in the subtree only, if it's less then search in the left subtree only. That's why the search is more efficient and have a complexity of O(log N)
3. Though a BST is there to endure the searching efficiency, still it can result in a skew tree like below:
   
   The above tree is a right skew tree and each node has only the right child. So though it's a BST, searching will have complexity O(h) which is O(n) in this case.
   
   The above tree is a left skew tree and each node has only the left child. So though it's a BST, searching will have complexity O(h) which is O(n) in this case.

Binary Search Tree Tutorial

Basic

1. Insertion in a Binary Search Tree
2. Deletion in Binary Search Tree (BST)
3. Comparison between Hash Table and Binary Search Tree

Construction & Conversion

1. Construct BST from Given Preorder Traversal
2. Construct a binary search tree from a sorted linked list
3. Construct a binary search tree from a sorted 1-D array
4. Convert given Binary Search Tree to a Greater Sum Tree
5. Convert given Binary Search Tree to a Smaller Sum Tree
6. Construct all possible BSTs with keys 1 to N
7. Convert a Binary Search Tree into a min-heap
8. Construct BST from level order traversal
9. Convert an unbalanced BST to a balanced BST
10. Find the Minimum and Maximum node in a Binary Search Tree
11. Check if the given array can represent Preorder Traversal of a Binary Search Tree
12. Kth Minimum in a Binary Search Tree
13. Kth Maximum in a Binary Search Tree

Checking & Searching

1. Check if given sorted subsequence exits in the Binary Search Tree or Not
2. Check if the Binary Search Tree contains a dead end
3. Check if the given array can represent inorder traversal of a BST
4. Check if two BSTs have same set of elements or not
5. Largest Element in the BST less than or Equal to N
6. Distance between two nodes in a BST
7. Count Number of pairs from two different BSTs whose sum is equal to X
8. Merge Two Binary Search Trees Set 1
9. Merge two Binary Search Trees set 2 (limited space)
10. Floor and ceil of an element in an array using C++
11. Two Elements whose sum is closest to zero
12. Find a pair with a given difference
13. Count number of occurrences (or frequency) in a sorted array
14. Find a Fixed Point (Value equal to index) in a given array
15. Find the maximum element in an array which is first increasing and then decreasing