**Table of Contents**hide

## 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

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.

## Advantages

- 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.

## Disadvantages

- 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.

## 0 Comments