Binary Search Tree


What is tree data structure?

The tree is a type of data structure that represents data hierarchically. Trees are a collection of nodes with a root node, and every node is connected to its parent node using edges. Every node has only one parent in a tree but can have multiple child nodes. Types of the tree are as follows:

  1. General tree: The tree with no restriction of the number of child nodes is known as the general tree.
  2. Binary tree: A binary tree is a tree in which a node can have at most two nodes.

Binary Search Tree

A binary search tree is a class of binary trees in which the nodes are arranged in a specific manner so that it is known as an ordered binary tree. In binary search trees, the value of left nodes is always less than the value of right nodes and root nodes.

Left_node < root >= Right_node

On binary search tree the following five operations get performed,

  1. Insertion
  2. Searching
  3. Inorder traversal
  4. Preorder traversal
  5. Postorder traversal

Advantages of binary search tree

  1. As the tree is divided into two sections, the searching process gets easy.
  2. A binary search tree is considered a very efficient data structure; it removes half of the binary tree at each step. The time complexity is o(log2n) of sorting.
  3. Speed of insertion and deletion is very good.