Binary Search Tree (Introduction)

April 14, 2020

Introduction to Binary Search Tree (BST)

  1. A binary search tree can be defined as a data structure that essentially fulfills the following properties:
    • The left subtree must contain all the nodes containing  the values less than the root node.
    • The right subtree must contain all the nodes containing the values more than the root node.
    • Each of the left and the right subtrees must be a binary tree itself.
  2. It is a binary tree structure which keeps the data in a sorted order so as to fulfill the binary tree properties.
  3. When searching for a particular element in a tree, it traverses from the root node to the leaf making comparisons between the nodes so as to determine the basis and the course of the search operation, i.e ,whether to look in the left subtree or the right subtree.
  4. The BST divides the tree into two segments; the left subtree and the right subtree such that:

left_subtree(data) < root node < right_subtree(data).

Representation of a BST

The representation of a BST is similar to that of a binary tree. The order of a BST is ‘2’. Each node can have at most two children.

The only difference between the two is that there is a certain criteria of arrangement or insertion of the elements based on their comparisons with the root node and the sub tree segment they are added to.

For example: [ 15 , 18 , 13 , 8 , 19 , 4 , 16 , 9 , 14 ]

Here we can see, 15 becomes the root node and all the elements  lesser than 15 are sorted in the left sub tree and and all the elements greater than 15 are sorted in the right sub tree.

Operations in a BST

  1. Traversal
  2. Insertion
  3. Deletion

Features of a BST

  1. Fast look-up.
  2. Efficient addition and removal of items.
  3. Used to implement dynamic set of items.