Binary Search Tree

   Last Updated: 06 October, 2024       🕓  5 Mins

A tree is a hierarchical data structure that consists of nodes connected by edges. Each node contains a value and may have zero or more child nodes. The topmost node is called the root node, and the nodes at the bottom are called leaf nodes.

What is Binary Search Tree?

A Binary Search Tree (BST) is a special type of data structure that organizes data in a tree-like structure. It has a single starting node called the root, and each node can have at most two child nodes: a left child and a right child.

In BST, the value of each node is greater than all the values in its left subtree and less than all the values in its right subtree. This ordering property makes BSTs efficient for searching, inserting, and deleting elements.

In the tree above, 50 is the Root node and it has two child nodes 30 (create left subtree) and 70 (create right subtree).

Important points of Binary Search Tree (BST):

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtrees must be binary search tree (BST).
• Duplicate nodes are not allowed (but BST may have duplicate values handled differently).

Operations On Binary Search Tree (BST)

We can perform the following types of operations on the BST:

1. Insert a node
2. Delete a node
3. Search a node
4. Traversal