Binary search tree in data structure

A binary search tree is one of the variants of the binary tree, also known as an ordered binary tree, in which the nodes are arranged in order by some rule mentioned below.

Node of binary search tree follows order mentioned below

  1. The value of all nodes in the left sub-tree or left child should be lesser than its root node value.
  2. The value of all nodes in the right sub-tree or right child should be greater than or equal to its root value.
  3. Each node should follow the above two rules at every height of the Binary search tree i.e., we can say that this rule will be recursively applied to all the left and right sub-trees of the root.

Binary search tree maintains

left_subtree (keys) < node (key) < right_subtree (keys)

  • A binary search tree can be empty.
  • The node of the binary search tree may contain both numerical as well as a string value.
  • Binary Search Tree Numerical Order.
  • Binary Search Tree Lexicographical Order.

Binary search tree operations

Search

Searches an element in a tree.

Insert

Inserts an element in a tree.

Pre-order Traversal

Traverse a tree in a pre-order manner means first to traverse the Root node, then the Left node, and at last Right node.

Traverse format : (Root, Left, Right)

In-order Traversal

Traverse a tree in an in-order manner means first to traverse the Left node, then the root node, and then at last Right node.

Traverse format : (Left, Root, Right)

Post-order Traversal

Traverse a tree in a post-order manner means the first traverse left node, then the right node, and the last root node.

Traverse format : (Left, Right, Root)

Advantages of using a binary search tree

  • In BST, we get a hint at each step about elements while we perform a searching operation for an element.
  • In the best case for searching an element, it takes o(log2n) time, and in the worst case, it takes 0(n) to search an element. This complexity is much better than the array and linked list for the same operation.

Share on