## Introduction of Binary Search Tree

• They are also called Ordered Binary Trees as each node in BST is placed according to a specific order.

## Definition

• A binary search tree is a non-linear, non-cyclic data structure and is an extension/type of binary tree that may be empty, or each node has at most two children.
• A binary search tree is either empty or it contains a root node together with two binary search trees called the left subtree and the right subtree of the root.

## Characteristics

• A BST is said to be perfectly balanced if for every internal node, there are equal number of nodes in its left and right sub-trees.
• Degenerate Binary Search Tree is a BST in which all the elements are arranged in one side only i.e., either left or right side only.
• Each node in the BST is itself a BST i.e., BST is naturally recursive in nature.

## Properties

• Each node in BST has <= 2 children.
• The left subtree of a node contains only nodes with keys lesser than the node’s key i.e. All keys in left subtree are smaller than node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key i.e. All keys in right subtree are larger than node’s key.
• The left and right subtree each must also be a binary search tree.

## Implementation/Representation of BST

• The node of a typical BST can be represented as –
struct bst
{
string data; int value;     //root node
struct bst  * left;             // left subtree
struct bst  * right;          // right subtree
};

## Operation in BST

• There are some common operations usually seen in a typical BST. These are –
• Creation of new/fresh BST.
• Traversing/Printing the node values in BST.
• Insertion of a new node in the existing BST.
• Deletion of one/more node from an existing BST.
• Finding/Searching specific node value from an existing BST.
##### Algorithm for Deletion of the node from an existing BST:-
• A binary search tree (BST) is a binary tree data structure where each node has at most two children, and the values in the left subtree of a node are less than or equal to the node’s value, while the values in the right subtree are greater than the node’s value.
• Deleting a node from a BST involves maintaining the property of BST while removing the desired node.
• The step-by-step algorithm for deleting a node from a BST is as follows:
Step 1: Start at the root of the tree.
Step 2: Search for the node to delete:
• If the node to delete has a value less than the current node’s value, move to the left subtree.
• If the node to delete has a value greater than the current node’s value, go to the right subtree.
• If the current node’s value is equal to the value of the node to delete, we have found the node to delete.
Step 3: Once we have found the node to delete, there are three conditions/cases to consider:
a. Node having no children (leaf/terminal node):
• Simply remove the node from the tree.
b. Node with one child either left or right:
• Replace the root node to delete with its only child. If it has the left child, replace it with the left child value; if it has the right child, replace it with the right child value.
c. Node with two children:
• When the node with two children is deleted, its place is filled with either a left subtree(the largest node) value or a right subtree (the smallest)value and re-adjusting using the BST rule.

## Traversal/Printing in BST

• Traversal is a visit to every node in the BST and perform some specific
operation on it to get the stored values.
• There are three universal steps occur in BST traversal in different order. These are –
1. Visit the root node.
2. Traverse its left (associated) subtree.
3. Traverse its right (associated) subtree
• There are 3 common types of traversals in BST. These are –
(a) Pre-Order Traversal
The order of traversal in pre-order traversal is-

1. Visit the root node first.
2. Now, Traverse its left (associated) subtree.
3. Then, Traverse its right (associated) subtree

(b) In-Order Traversal
The order of traversal in In-order traversal is-
1. Traverse the left (associated) subtree first.
2. Now, visit the root node.
3. Then, traverse the right (associated) subtree
(c) Post-Order Traversal
The order of traversal in post-order traversal is-
1.Traverse the left (associated) subtree first.
2. Now, traverse the right (associated) subtree.
3. Then, visit the root node.
Level-Order Traversal:
• Here, each node of the BST is traversed level by level (top to bottom) in order of its appearance/location.
• In each level, traversing order is from left to right.

• Searching is very effective and becomes very easy due to arrangement of data one-sided i.e., smaller than root is in left side and higher in right side.
• The arrangement of all the nodes of BST in a specific order.
• BST has an efficient & effective working when compared to arrays and linked lists.
• Insertion and deletion operations are comparatively faster than other data structures like linked lists and arrays.

• An imbalanced or degenerated form of BST has less usability and more complex.

## Use/Applications

Some major/important applications of BST are as follows: –

• BST is used to implement multilevel indexing structure in database applications to handle a large no. of data items.
• BST is also used in applications that require a sorted list as input like the online stores.
• BST is used to implement Huffman coding algorithm.
• BSTs are also used to evaluate the expression by constructing expression trees.
• BST is also used in the construction of digital dictionary.
• BST can also be used to implement various efficient searching algorithms.
Categories: Tree