Introduction to Binary Search Tree - The Coding Shala

Last Updated: 19-Jan-2021
Home >> Data Structures >> Binary Search Tree

 In this post, we will learn the basic Introduction of the Binary Search Tree.

Binary Search Tree

A binary search tree(BST), a special form of a binary tree that satisfies the following property:
  • The value in each node must be greater than(or equal to) any values stored in its left subtree.
  • The value in each node must be less than(or equal to) any values stored in its right subtree.
The following is an example of a binary search tree:

    5
       / \
      2   6
     / \   \
    1   4   7
       /
      3

Like any other data structure, binary search trees(BSTs) support three main operations: search, insertion, and deletion. 

Search in Binary Search Tree

To search a node in the Binary search tree we can
  • Return the node if the target value is equal to the value of the node.
  • Continue searching in the left subtree if the target value is less than the value of the node.
  • Continue searching in the right subtree if the target value is larger than the value of the node.

Insertion in the Binary Search Tree

Another common operation in BST is to insert a new node. The main idea to insert a node is first we found out a proper leaf position for the target node and then insert the node as a leaf.

To insert a node we will:
  • Search the left or right subtree according to the relation of the value of our target node.
  • Repeat the above step until reaching an external node.
  • Add the new node as its left or right child depending on the relation of the value of the node and the value of our target node.

Deletion in a Binary Search Tree

Deletion is more complicated than the insertion and searching in BST. There are three different cases while we delete a node.
  1. If the target node has no child then we can simply remove the node.
  2. If the target node has one child, we can use its child to replace itself.
  3. If the target node has two children, replace the node with its in-order successor or predecessor node and delete that node.

Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Anti Diagonals - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala