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
 All node values must be distinct
 Parent value must be greater than the left child value and smaller than the right child value
 Both the left and right subtree needs to be Binary search tree as well
 All the node in the left subtree of the root has less key/node value than the root
 All the node in the right subtree of the root has greater key/node value than the root
Examples:

BST:
Below is the example of a BST as it maintains all the properties.

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:
 Insert a Node (Insertion in a Binary Search Tree)
 Delete a Node (Deletion in Binary Search Tree)
 Search a Node
 Find Minimum node value
 Find Maximum node value
Few More Interesting Points/Properties
 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.
 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)

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
 Insertion in a Binary Search Tree
 Deletion in Binary Search Tree (BST)
 Comparison between Hash Table and Binary Search Tree
Construction & Conversion
 Construct BST from Given Preorder Traversal
 Construct a binary search tree from a sorted linked list
 Construct a binary search tree from a sorted 1D array
 Convert given Binary Search Tree to a Greater Sum Tree
 Convert given Binary Search Tree to a Smaller Sum Tree
 Construct all possible BSTs with keys 1 to N
 Convert a Binary Search Tree into a minheap
 Construct BST from level order traversal
 Convert an unbalanced BST to a balanced BST
 Find the Minimum and Maximum node in a Binary Search Tree
 Check if the given array can represent Preorder Traversal of a Binary Search Tree
 Kth Minimum in a Binary Search Tree
 Kth Maximum in a Binary Search Tree
Checking & Searching
 Check if given sorted subsequence exits in the Binary Search Tree or Not
 Check if the Binary Search Tree contains a dead end
 Check if the given array can represent inorder traversal of a BST
 Check if two BSTs have same set of elements or not
 Largest Element in the BST less than or Equal to N
 Distance between two nodes in a BST
 Count Number of pairs from two different BSTs whose sum is equal to X
 Merge Two Binary Search Trees Set 1
 Merge two Binary Search Trees set 2 (limited space)
 Floor and ceil of an element in an array using C++
 Two Elements whose sum is closest to zero
 Find a pair with a given difference
 Count number of occurrences (or frequency) in a sorted array
 Find a Fixed Point (Value equal to index) in a given array
 Find the maximum element in an array which is first increasing and then decreasing