# How to use Binary Search Tree (BST) in C / C++

In this tutorial, we will learn about **how to use Binary Search Tree in C / C++** and its working with the help of some examples. This is one of the basic knowledge in C / C++ programming language, so please learn it carefully.

Before learning about Binary Search Tree in C / C++, let's learn about binary tree data structure.

## What is a Binary Tree in C / C++?

Let us take a real example for you to understand the tree structure.

**Example:** The tree structure is similar to how we organize folders in a computer. Outside is the parent folder, inside contains sub-folders.

A binary tree gathers many nodes together. Each node consists of three components:

**Data:**The value of a node is stored in a binary search tree.**Left pointer:**This is a pointer, it points to the binary tree on the left.- R
**ight pointer:**This is a pointer, it points to the binary tree on the right.

## What is a Binary Search Tree in C / C++?

The nodes in the binary search tree must comply with the following rules:

- The node to the left is always smaller than the node immediately above it.
- The node to the right is always larger than the node immediately above it.

## How does a Binary Search Tree in C / C++ work?

To illustrate how binary search tree in C / C++ work. We have an example below.

**Example: **Suppose we have a binary search tree. Now we will insert nodes with values 27, 14, 35, 10, 19, 31, 42 into the binary search tree. Then the storage process is done as follows.

**Explain:**

- The number 27 is stored in the tree, this is the
`key`

used to compare with the following elements. - The number 14 is compared with the number 27 (
*key*). Since`14 < 27`

, the number 14 is stored to the left of 27. - The number 35 is compared with the number 27 (
*key*). Since`35 > 27`

, the number 35 is stored to the right of 27. `10 < 27`

and`10 < 14`

. So 10 is stored to the left of 14.`19 < 27`

and`19 > 14`

. So 19 is stored to the right of 14.`31 > 27`

and`31 < 35`

. So 31 is stored to the left of 35.`42 < 27`

and`42 > 35`

. So 42 is stored to the right of 35.

**Note**: The node with a value smaller than the node immediately above it will be saved to the left. Otherwise, if it is larger, it will be saved to the right.

## Insert node to Binary Search Tree in C / C++

Before insert a new node to the binary search tree in C / C++. We need to create the data structure of the binary search tree first.

struct node { int data; struct node *pLeft; struct node *pRight; }; /*Initialize a binary search tree*/ void Initialize(TREE &t) { t = NULL; }

To insert a new node to the binary search tree we have two cases.

**Case 1:**The binary search tree is empty, then the newly added node is the`key`

.**Case 2:**The binary search tree already has elements, then we need to compare it with the`key`

to store the new node.

void InsertNode(TREE &t, int x) { if (t == NULL) { NODE *p = new NODE; p->data = x; p->pLeft = NULL; p->pRight = NULL; t = p; } { if (t->data > x) { InsertNode(t->pLeft, x); } else if (t->data < x) { InsertNode(t->pRight, x); } } }

## How to traverse Binary Search Tree in C / C++

To traverse the binary search tree in C / C++, we have 6 ways to do it. Each way will give us a different result.

**Traversing the NLR (Node - Left - Right) binary search tree in C/C++:**

void Traverse_NLR(TREE t) { if (t != NULL) { cout << t->data << " "; Traverse_NLR(t->pLeft); Traverse_NLR(t->pRight); } }

**Traversing the NRL (Node - Right - Left) binary search tree in C/C++:**

void Traverse_NRL(TREE t) { if (t != NULL) { cout << t->data << " "; Traverse_NRL(t->pRight); Traverse_NRL(t->pLeft); } }

**Traversing the LNR (Left - Node - Right) binary search tree in C/C++:**

void Traverse_LNR(TREE t) { if (t != NULL) { Traverse_LNR(t->pLeft); cout << t->data << " "; Traverse_LNR(t->pRight); } }

To traverse a binary search tree in this way, the result will be a list of elements sorted in ascending order.

**Traversing the RNL (Right - Node - Left) binary search tree in C/C++:**

void Traverse_RNL(TREE t) { if (t != NULL) { Traverse_RNL(t->pRight); cout << t->data << " "; Traverse_RNL(t->pLeft); } }

To traverse a binary search tree in this way, the result will be a list of elements sorted in descending order.

**Traversing the LRN (Left - Right - Node) binary search tree in C/C++:**

void Traverse_LRN(TREE t) { if (t != NULL) { Traverse_LRN(t->pLeft); Traverse_LRN(t->pRight); cout << t->data << " "; } }

**Traversing the RLN (Right - Left - Node) binary search tree in C/C++:**

void Traverse_RLN(TREE t) { if (t != NULL) { Traverse_RLN(t->pRight); Traverse_RLN(t->pLeft); cout << t->data << " "; } }

## Remove node from Binary Search Tree in C / C++

To remove a node from the binary search tree, we have three cases as follows:

- The node to be deleted is the leaf node.
- The node to be deleted lies has a single child node.
- The node to be deleted has two children.

**Case 1:** The node to be deleted is the leaf node.

In this case, we just need to delete the node without taking any further action.

**Case 2:** The node to be deleted lies has a single child node.

- Replace that node with its child node.
- Remove the child node from its original position.

**Case 3:** The node to be deleted has two children.

- Get the inorder successor of that node.
- Replace the node with the inorder successor.
- Remove the in order successor from its original position.

Below is a function that deletes any node that we have written. You can refer.

void AlternativeNode(TREE &X, TREE &Y) { if (Y->pLeft != NULL) { AlternativeNode(X, Y->pLeft); } else { X->data = Y->data; X = Y; Y = Y->pRight; } } void RemoveNode(TREE &t, int data) { if (t == NULL) { return; } else { if (data < t->data) { RemoveNode(t->pLeft, data); } else if (data > t->data) { RemoveNode(t->pRight, data); } else { NODE *X = t; if (t->pLeft == NULL) { t = t->pRight; } else if (t->pRight == NULL) { t = t->pLeft; } else { AlternativeNode(X, t->pRight); } delete X; } } }

## Example of Binary Search Tree in C / C++

Here, we have an example that illustrates how to use binary search tree in C / C++. The program includes all the operations mentioned above.

#include<iostream> using namespace std; struct node { int data; struct node *pLeft; struct node *pRight; }; typedef struct node NODE; typedef NODE* TREE; void Initialize(TREE &t) { t = NULL; } void InsertNode(TREE &t, int x) { if (t == NULL) { NODE *p = new NODE; p->data = x; p->pLeft = NULL; p->pRight = NULL; t = p; } else { if (t->data > x) { InsertNode(t->pLeft, x); } else if (t->data < x) { InsertNode(t->pRight, x); } } } void Traverse_NLR(TREE t) { if (t != NULL) { cout << t->data << " "; Traverse_NLR(t->pLeft); Traverse_NLR(t->pRight); } } void Traverse_NRL(TREE t) { if (t != NULL) { cout << t->data << " "; Traverse_NRL(t->pRight); Traverse_NRL(t->pLeft); } } void Traverse_LNR(TREE t) { if (t != NULL) { Traverse_LNR(t->pLeft); cout << t->data << " "; Traverse_LNR(t->pRight); } } void Traverse_RNL(TREE t) { if (t != NULL) { Traverse_RNL(t->pRight); cout << t->data << " "; Traverse_RNL(t->pLeft); } } void Traverse_LRN(TREE t) { if (t != NULL) { Traverse_LRN(t->pLeft); Traverse_LRN(t->pRight); cout << t->data << " "; } } void Traverse_RLN(TREE t) { if (t != NULL) { Traverse_RLN(t->pRight); Traverse_RLN(t->pLeft); cout << t->data << " "; } } void AlternativeNode(TREE &X, TREE &Y) { if (Y->pLeft != NULL) { AlternativeNode(X, Y->pLeft); } else { X->data = Y->data; X = Y; Y = Y->pRight; } } void RemoveNode(TREE &t, int data) { if (t == NULL) { return; } else { if (data < t->data) { RemoveNode(t->pLeft, data); } else if (data > t->data) { RemoveNode(t->pRight, data); } else { NODE *X = t; if (t->pLeft == NULL) { t = t->pRight; } else if (t->pRight == NULL) { t = t->pLeft; } else { AlternativeNode(X, t->pRight); } delete X; } } } int main() { TREE t; Initialize(t); int n, k, x; cout<<"Enter the number of elements in the tree: "; cin>>n; cout<<"Enter values for the elements.\n"; for(int i = 1; i <= n; i++){ cout<<"The value of element "<<i<<": "; cin>>k; InsertNode(t,k); } cout<<"\nTraversing the NLR: "; Traverse_NLR(t); cout<<"\nTraversing the NRL: "; Traverse_NRL(t); cout<<"\nTraversing the LNR: "; Traverse_LNR(t); cout<<"\nTraversing the RNL: "; Traverse_RNL(t); cout<<"\nTraversing the LRN: "; Traverse_LRN(t); cout<<"\nTraversing the RLN: "; Traverse_RLN(t); cout<<"\n\nEnter the value to remove: "; cin>>x; RemoveNode(t, x); cout<<"\nElements in the tree after deletion: "; Traverse_NLR(t); cout<<"\n-------------------------------\n"; cout<<"This program is posted at learnnc.com"; return 0; }

Output: