​ ​ ​ ​ MODULE - 4

4.1 Binary tree: A Binary Tree Data Structure is a hierarchical data structure
in which each node has at most two children, referred to as the left child and the
right child. The topmost node in a binary tree is called the root, and the
bottom-most nodes are called leaves.

4.1.1 Representation of Binary Tree: Each node in a Binary Tree has three parts:
●​ Data
●​ Pointer to the left child
●​ Pointer to the right child

The restriction, that a node can have a maximum of two child nodes, gives us many
benefits:
●​ Algorithms like traversing, searching, insertion and deletion become easier
to understand, to implement, and run faster.
●​ Keeping data sorted in a Binary Search Tree (BST) makes searching very
efficient.
●​ Balancing trees is easier to do with a limited number of child nodes, using an
AVL Binary Tree for example.
●​ Binary Trees can be represented as arrays, making the tree more memory
efficient.

4.1.2 Terminologies in Binary Tree:

●​ Nodes: The fundamental part of a binary tree, where each node contains data
and link to two child nodes.
●​ Root: The topmost node in a tree is known as the root node. It has no parent
and serves as the starting point for all nodes in the tree.
●​ Parent Node: A node that has one or more child nodes. In a binary tree, each
node can have at most two children.
●​ Child Node: A node that is a descendant of another node (its parent).
●​ Leaf Node: A node that does not have any children or both children are null.
●​ Internal Node: A node that has at least one child. This includes all nodes
except the root and the leaf nodes.
●​ Height of a Binary Tree: The number of nodes from the deepest leaf node to
the root node.

4.1.3 Properties of a binary tree:

●​ The maximum number of nodes at level ‘L’ of a binary tree is 2L.
●​ The Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1.
●​ In a Binary Tree with N nodes, the minimum possible height or the
minimum number of levels is Log2(N+1).
●​ A Binary Tree with L leaves has at least | Log2 L |+ 1 levels.
●​ In a Binary tree where every node has 0 or 2 children, the number of leaf
nodes is always one more than nodes with two children.
●​ In a non-empty binary tree, if n is the total number of nodes and e is the total
number of edges, then e = n-1.

How to Create/Declare a Node of a Binary Tree?

// Structure of each node of the tree.
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Note: Unlike other languages, C does not support Object
Oriented Programming. So, we need to write a separate
method for create and instance of tree node
struct Node* newNode(int item) {
struct Node* temp =
(struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

Example for Creating a Binary Tree:

Here’s an example of creating a Binary Tree with four nodes (2, 3, 4, 5)
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *left;
struct Node *right;
};

struct Node* createNode(int d) {

struct Node* newNode =
(struct Node*)malloc(sizeof(struct Node));
newNode->data = d;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

int main() {
// Initialize and allocate memory for tree nodes
struct Node* firstNode = createNode(2);
struct Node* secondNode = createNode(3);
struct Node* thirdNode = createNode(4);
struct Node* fourthNode = createNode(5);

// Connect binary tree nodes

firstNode->left = secondNode;
firstNode->right = thirdNode;
secondNode->left = fourthNode;
 return 0;
}

In the Previous code, we have created four tree nodes firstNode, secondNode,
thirdNode and fourthNode having values 2, 3, 4 and 5 respectively.
●​ After creating three nodes, we have connected these nodes to form the tree
structure like mentioned shown in above image.
●​ Connect the secondNode to the left of firstNode by firstNode->left =
secondNode
●​ Connect the thirdNode to the right of firstNode by firstNode->right =
thirdNode
●​ Connect the fourthNode to the left of secondNode by secondNode->left =
fourthNode

4.2 Types of Binary Tree:

●​ On the basis of Number of Children
●​ Full Binary Tree: A full binary tree is a binary tree with either zero or
two child nodes for each node.
●​ Degenerate Binary Tree: Every non-leaf node has just one child in a
binary tree known as a Degenerate Binary tree. The tree effectively
transforms into a linked list as a result, with each node linking to its
single child.
●​ Skewed Binary Trees: A skewed binary tree is a type of binary tree in
which all the nodes have only either one child or no child.
●​ On the basis of Completion of Levels
●​ Complete Binary Tree: A complete binary tree is a special type of
binary tree where all the levels of the tree are filled completely except
the lowest level nodes which are filled from as left as possible.
●​ Perfect Binary Tree: A perfect binary tree is a special type of binary
tree in which all the leaf nodes are at the same depth, and all non-leaf
nodes have two children.
●​ On the basis of Node Values:
●​ Binary Search Tree: Binary Search Tree is a data structure used in
computer science for organizing and storing data in a sorted manner.
Binary search tree follows all properties of binary tree and for every
node, its left subtree contains values less than the node and the right
subtree contains values greater than the node.
 ●​ AVL Tree: An AVL tree defined as a self-balancing Binary Search
Tree (BST) where the difference between heights of left and right
subtrees for any node cannot be more than one.
●​ Red, Black Tree: A Red-Black Tree is a self-balancing binary search
tree where each node has an additional attribute: a color, which can be
either red or black. The primary objective of these trees is to maintain
balance during insertions and deletions, ensuring efficient data
retrieval and manipulation.
●​ B Tree: A B-tree is a self-balancing data structure that stores data in a
sorted order
●​ B+ Tree: B + Tree is a variation of the B-tree data structure. In a B +
tree, data pointers are stored only at the leaf nodes of the tree.
●​ Segment Tree: Segment Tree is a data structures that allows efficient
querying and updating of intervals or segments of an array.

4.3 Strictly binary tree: It is also called as a full binary tree.

Definition: A full binary tree is a type of binary tree in which every node has
either zero or two children.

Full Binary Tree example

Full Binary Tree Theorem:

Let T be a nonempty, full binary tree Then:
●​ If T has I internal nodes, the number of leaves is L = I + 1.
This is known as the full binary tree theorem.
Facts derived from the theorem:
●​ If T has I internal nodes, the total number of nodes is N = 2I + 1.
●​ If T has a total of N nodes, the number of internal nodes is I = (N – 1)/2.
●​ If T has a total of N nodes, the number of leaves is L = (N + 1)/2.
●​ If T has L leaves, the total number of nodes is N = 2L – 1.
●​ If T has L leaves, the number of internal nodes is I = L – 1.
4.4 Complete Binary Tree: A complete binary tree is a special type of
binary tree where all the levels of the tree are filled completely except the lowest
level nodes which are filled from as left as possible.

Properties of Complete Binary Tree:

●​ A complete binary tree is said to be a proper binary tree where all leaves
have the same depth.
●​ In a complete binary tree number of nodes at depth d is 2d.
●​ In a complete binary tree with n nodes height of the tree is log(n+1).
●​ All the levels except the last level are completely full.
Exercise: Check whether a binary tree is a full binary tree or not.
// C program to check whether a given Binary Tree is full or not
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

/* Tree node structure */

struct Node
{
​ int key;
​ struct Node *left, *right;
};

/* Helper function that allocates a new node with the given key and NULL left
and right pointer. */
struct Node *newNode(char k)
{
​ struct Node *node = (struct Node*)malloc(sizeof(struct Node));
​ node->key = k;
​ node->right = node->left = NULL;
​ return node;
}

/* This function tests if a binary tree is a full binary tree. */

bool isFullTree (struct Node* root)
{
​ // If empty tree
​ if (root == NULL)
​ ​ return true;

​ // If leaf node
​ if (root->left == NULL && root->right == NULL)
​ ​ return true;

​ // If both left and right are not NULL, and left & right subtrees are full
​ if ((root->left) && (root->right))
​ ​ return (isFullTree(root->left) && isFullTree(root->right));

​ // We reach here when none of the above if conditions work

​ return false;
}

// Driver Program
int main()
{
​ struct Node* root = NULL;
​ root = newNode(10);
​ root->left = newNode(20);
​ root->right = newNode(30);

​ root->left->right = newNode(40);
​ root->left->left = newNode(50);
​ root->right->left = newNode(60);
​ root->right->right = newNode(70);

​ root->left->left->left = newNode(80);
​ root->left->left->right = newNode(90);
​ root->left->right->left = newNode(80);
​ root->left->right->right = newNode(90);
​ root->right->left->left = newNode(80);
​ root->right->left->right = newNode(90);
​ root->right->right->left = newNode(80);
​ root->right->right->right = newNode(90);
​ if (isFullTree(root))
​ ​ printf("The Binary Tree is full\n");
​ else
​ ​ printf("The Binary Tree is not full\n");

​ return(0);
}

4.4 Representing binary tree in memory:

Binary trees can be represented in multiple ways, each with its own
advantages, depending on the use case. Let's explore the two common methods:
linked node representation and array implementation.

There are two primary ways to represent binary trees:

1.​ Linked Node Representation
2.​ Array Representation

Linked Node Representation:

In this representation, the binary tree is stored in the memory, in the
form of a linked list where the number of nodes is stored at noncontiguous
memory locations and linked together by inheriting parent child relationship
like a tree.
Every node contains three parts: pointer to the left node, data element
and pointer to the right node. Each binary tree has a root pointer which
points to the root node of the binary tree. In an empty binary tree, the root
pointer will point to null.
 ​
This representation is mostly used to represent binary tree with multiple
advantages and some disadvantages. The most common ones are given
below.
Advantages:
●​ It can easily grow or shrink as needed, so it uses only the memory it
needs.
●​ Adding or removing nodes is straightforward and requires only pointer
adjustments.
●​ Only uses memory for the nodes that exist, making it efficient for sparse
trees.

Disadvantages:
●​ Needs extra memory for pointers.
●​ Finding a node can take longer because you have to start from the root
and follow pointers.
Array Representation
Array Representation is another way to represent binary trees, especially useful
when the tree is complete (all levels are fully filled except possibly the last, which
is filled from left to right).

Rules to determine the locations of the parent, left child and right child of any
node I in the binary tree using array.
●​ Store the root node in the first location of the array TREE.
●​ If a node is present in the location I of the array TREE, then store its left
child in the location 2* I
●​ If a node is present in the location I of the array TREE, then store its right
child in the location 2* I+1.
Advantages:
●​ This representation is very easy to understand.
●​ This is the best representation for complete and full binary tree
representation.
●​ Programming is very easy.
●​ It is very easy to move from a child to its parents and vice versa.

Disadvantages:

●​ Lot of memory area wasted.

●​ Insertion and deletion of nodes needs lot of data movement.
●​ Execution time high.
●​ This is not suited for trees other than full and complete tree.

Comparison of Linked list vs Array Representation of Binary Tree:

Linked Node Array
Feature Representation Representation
Uses extra memory for Efficient for
Memory Usage
pointers complete trees
Ease of Simple but limited to
Simple and intuitive
Implementation complete trees
Not flexible for
Dynamic Size Easily grows and shrinks
dynamic sizes
Slower access for specific Fast access using
Access Time
nodes indices
Suitable For Any binary tree structure Complete binary tree
4.5 Traversing a binary tree:

Tree Traversal refers to the process of visiting or accessing each node of the tree
exactly once in a certain order. Tree traversal algorithms help us to visit and
process all the nodes of the tree. Since tree is not a linear data structure, there are
multiple nodes which we can visit after visiting a certain node.
A Tree Data Structure can be traversed in following ways:
●​ Depth First Search or DFS
o​ Inorder Traversal
o​ Preorder Traversal
o​ Postorder Traversal
●​ Level Order Traversal or Breadth First Search or BFS
1.​ Inorder traversal visits the node in the order: Left -> Root -> Right

2.​ Preorder traversal visits the node in the order: Root -> Left -> Right

3.​Postorder traversal visits the node in the order: Left -> Right -> Root
4.​Level Order Traversal visits all nodes present in the same level completely
before visiting the next level.

All types are mentioned in the below image.

Write a program for In-Order Binary tree traversal.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};

void inOrderTraversal(struct Node* root) {

if (root == NULL) return;

// Traverse the left subtree

inOrderTraversal(root->left);

// Visit the root node

printf("%d ", root->data);

// Traverse the right subtree

inOrderTraversal(root->right);
}

struct Node* newNode(int data) {

struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

int main() {
struct Node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
 printf("In-Order Traversal: ");
inOrderTraversal(root);
printf("\n");

return 0;
}

Ouput In-Order Traversal: 4 1 5 2 3

Write a Program for Pre-Order Binary Tree Traversal.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};

void preOrderTraversal(struct Node* root) {

if (root == NULL) return;

// Visit the root node

printf("%d ", root->data);

// Traverse the left subtree

preOrderTraversal(root->left);

// Traverse the right subtree

preOrderTraversal(root->right);
}

struct Node* newNode(int data) {

struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
 node->right = NULL;
return node;
}

int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5

struct Node* root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Pre-Order Traversal: ");

preOrderTraversal(root);
printf("\n");

return 0;
}
Output Pre-Order Traversal: 1 2 4 5 3

Write a Program for Post-Order Binary Tree Traversal.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};

void postOrderTraversal(struct Node* root) {

if (root == NULL) return;
 // Traverse the left subtree
postOrderTraversal(root->left);

// Traverse the right subtree

postOrderTraversal(root->right);

// Visit the root node

printf("%d ", root->data);
}

struct Node* newNode(int data) {

struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

int main () {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5

struct Node* root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Post-Order Traversal: ");

postOrderTraversal(root);
printf("\n");

return 0;
}
Output Post-Order Traversal: 4 5 2 3 1

4.6 Binary Search Tree: A BST is a type of Binary Tree data structure,
where the following properties must be true for any node "X" in the tree:

●​ The X node's left child and all of its descendants (children, children's
children, and so on) have lower values than X's value.
●​ The right child, and all its descendants have higher values than X's value.
●​ Left and right subtrees must also be Binary Search Trees.

These properties make it faster to search, add and delete values than a regular
binary tree.

Properties of Binary Search Tree:

●​ 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 subtree each must also be a binary search tree.
●​ There must be no duplicate nodes (BST may have duplicate values with
different handling approaches).

Example: Check whether the given tree is BST or not

4.6.1 Searching for a value in a BST:

●​ Searching for a value in a BST is very similar to how we found a value
using Binary Search on an array.
●​ For Binary Search to work, the array must be sorted already, and
searching for a value in an array can then be done really fast.
●​ Similarly, searching for a value in a BST can also be done really fast
because of how the nodes are placed.
 How it works:
1.​ Start at the root node.
2.​ If this is the value we are looking for, return.
3.​ If the value we are looking for is higher, continue searching in the right
subtree.
4.​ If the value we are looking for is lower, continue searching in the left
subtree.
5.​ If the subtree we want to search does not exist, depending on the
programming language, return None, or NULL, or something similar, to
indicate that the value is not inside the BST.

Code to implement Search in BST:

#include <stdio.h>
#include <stdlib.h>

struct Node {
int key;
struct Node* left;
struct Node* right;
};

// Constructor to create a new BST node

struct Node* newNode(int item)
{
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// function to search a key in a BST

struct Node* search(struct Node* root, int key)
{

// Base Cases: root is null or key is

 // present at root
if (root == NULL || root->key == key)
return root;

// Key is greater than root's key

if (root->key < key)
return search(root->right, key);

// Key is smaller than root's key

return search(root->left, key);
}

// Driver Code
int main()
{
// Creating a hard coded tree for keeping
// the length of the code small. We need
// to make sure that BST properties are
// maintained if we try some other cases.
struct Node* root = newNode(50);
root->left = newNode(30);
root->right = newNode(70);
root->left->left = newNode(20);
root->left->right = newNode(40);
root->right->left = newNode(60);
root->right->right = newNode(80);

printf(search(root, 19) != NULL ? "Found\n"

: "Not Found\n");
printf(search(root, 80) != NULL ? "Found\n"
: "Not Found\n");

return 0;
}
Output Not Found
Found
4.6.2 Insertion in Binary Search Tree (BST):
A new key is always inserted at the leaf by maintaining the property of the binary
search tree. We start searching for a key from the root until we hit a leaf node.
Once a leaf node is found, the new node is added as a child of the leaf node. The
below steps are followed while we try to insert a node into a binary search tree:
●​ Initialize the current node (say, currNode or node) with root node.
●​ Compare the key with the current node.
●​ Move left if the key is less than or equal to the current node value.
●​ Move right if the key is greater than current node value.
●​ Repeat steps 2 and 3 until you reach a leaf node.
●​ Attach the new key as a left or right child based on the comparison with
the leaf node’s value.

Below are the images showing steps to insert new node

Insertion in Binary Search Tree using Recursion:
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a BST node

struct Node {
int key;
struct Node* left;
struct Node* right;
};

// Function to create a new BST node

struct Node* newNode(int item) {
struct Node* temp =
(struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// Function to insert a new node with the given key

struct Node* insert(struct Node* node, int key) {

// If the tree is empty, return a new node

if (node == NULL)
return newNode(key);

// If the key is already present in the tree,return the node

if (node->key == key)
return node;

// Otherwise, recur down the tree. If the key to be inserted is greater than the
//node's key,insert it in the right subtree
if (node->key < key)
node->right = insert(node->right, key);

// If the key to be inserted is smaller than the node's key,insert it in the left
//subtree
 else
node->left = insert(node->left, key);

// Return the (unchanged) node pointer

return node;
}

// Function to perform inorder tree traversal

void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

// Driver program to test the above functions

int main() {
// Creating the following BST
// 50
// / \
// 30 70
// / \ / \
// 20 40 60 80

struct Node* root = newNode(50);

root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);

// Print inorder traversal of the BST

inorder(root);

return 0;
}​
Output 20 30 40 50 60 70 80
Insertion in Binary Search Tree using Iterative approach:
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a BST node

struct Node {
int key;
struct Node* left;
struct Node* right;
};

// Function to create a new BST node

struct Node* newNode(int item) {
struct Node* temp =
(struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

struct Node* insert(struct Node* root, int x)

{

struct Node* temp = newNode(x);

// If tree is empty
if (root == NULL)
return temp;

// Find the node who is going to have the new node temp as
// it child. The parent node is mainly going to be a leaf node
struct Node *parent = NULL, *curr = root;
while (curr != NULL) {
parent = curr;
if (curr->key > x)
curr = curr->left;
else if (curr->key < x)
curr = curr->right;
else
 return root;
}

// If x is smaller, make it left child, else right child

if (parent->key > x)
parent->left = temp;
else
parent->right = temp;
return root;
}

// Function to perform inorder tree traversal

void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

// Driver program to test the above functions

int main() {
// Creating the following BST
// 50
// / \
// 30 70
// / \ / \
// 20 40 60 80

struct Node* root = newNode(50);

root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);

// Print inorder traversal of the BST

inorder(root);
 return 0;
}​
Output 20 30 40 50 60 70 80

4.6.3 Deletion in Binary Search Tree (BST):

Given a BST, the task is to delete a node in this BST, which can be broken down
into 3 scenarios.
How it works:
●​ If the node is a leaf node, remove it by removing the link to it.
●​ If the node only has one child node, connect the parent node of the node you
want to remove to that child node.
●​ If the node has both right and left child nodes: Find the node's in-order
successor, change values with that node, then delete it.

Case 1. Delete a Leaf Node in BST

Case 2. Delete a Node with Single Child in BST: Deleting a single child node is
also simple in BST. Copy the child to the node and delete the node.
Case 3. Delete a Node with Both Children in BST:​
Deleting a node with both children is not so simple. Here we have to delete the
node is such a way, that the resulting tree follows the properties of a BST. The trick
is to find the inorder successor of the node. Copy contents of the inorder successor
to the node and delete the inorder successor.

Recursive Implementation of Deletion operation in a BST:

#include <stdio.h>
#include <stdlib.h>

struct Node {
int key;
struct Node* left;
struct Node* right;
};

// Note that it is not a generic inorder successor function. It mainly works when
//the right child is not empty, which is the case we need in BST delete.
struct Node* getSuccessor(struct Node* curr) {
curr = curr->right;
while (curr != NULL && curr->left != NULL)
curr = curr->left;
return curr;
}

// This function deletes a given key x from the given BST and returns the
//modified root of the BST (if it is modified)
struct Node* delNode(struct Node* root, int x) {
 // Base case
if (root == NULL)
return root;

// If key to be searched is in a subtree

if (root->key > x)
root->left = delNode(root->left, x);
else if (root->key < x)
root->right = delNode(root->right, x);
else {
// If root matches with the given key Cases when root has 0 children or
// only right child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}

// When root has only left child

if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

// When both children are present

struct Node* succ = getSuccessor(root);
root->key = succ->key;
root->right = delNode(root->right, succ->key);
}
return root;
}

struct Node* createNode(int key) {

struct Node* newNode =
(struct Node*)malloc(sizeof(struct Node));
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}

// Utility function to do inorder traversal

void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

// Driver code
int main() {
struct Node* root = createNode(10);
root->left = createNode(5);
root->right = createNode(15);
root->right->left = createNode(12);
root->right->right = createNode(18);
int x = 15;

root = delNode(root, x);

inorder(root);
return 0;
}​
Output 5 10 12 18

Implement a C program to insert, delete, and search elements in a Binary

Search Tree (BST).

#include <stdio.h>

#include <stdlib.h>

// Structure for a node in the BST

struct Node {
 int data;

struct Node* left;

struct Node* right;

};

// Create a new node

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode->left = newNode->right = NULL;

return newNode;

// Insert a node into the BST

struct Node* insert(struct Node* root, int value) {

if (root == NULL)

return createNode(value);

if (value < root->data)

root->left = insert(root->left, value);

 else if (value > root->data)

root->right = insert(root->right, value);

return root;

// Search for a value in the BST

struct Node* search(struct Node* root, int key) {

if (root == NULL || root->data == key)

return root;

if (key < root->data)

return search(root->left, key);

else

return search(root->right, key);

// Find minimum node in a subtree

struct Node* findMin(struct Node* root) {

while (root && root->left != NULL)

root = root->left;

return root;
}

// Delete a node from the BST

struct Node* delete(struct Node* root, int key) {

if (root == NULL)

return root;

if (key < root->data)

root->left = delete(root->left, key);

else if (key > root->data)

root->right = delete(root->right, key);

else {

// Node found

if (root->left == NULL) {

struct Node* temp = root->right;

free(root);

return temp;

} else if (root->right == NULL) {

struct Node* temp = root->left;

free(root);

return temp;

}
 // Node with two children

struct Node* temp = findMin(root->right);

root->data = temp->data;

root->right = delete(root->right, temp->data);

return root;

// Inorder traversal

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

printf("%d ", root->data);

inorder(root->right);

// Main function

int main() {

struct Node* root = NULL;

int choice, value;

while (1) {

printf("\n--- Binary Search Tree Menu ---\n");

printf("1. Insert\n2. Delete\n3. Search\n4. Inorder Traversal\n5. Exit\n");

printf("Enter choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter value to insert: ");

scanf("%d", &value);

root = insert(root, value);

break;

case 2:

printf("Enter value to delete: ");

scanf("%d", &value);

root = delete(root, value);

break;

case 3:
 printf("Enter value to search: ");

scanf("%d", &value);

if (search(root, value))

printf("Value %d found in the BST.\n", value);

else

printf("Value %d not found.\n", value);

break;

case 4:

printf("Inorder Traversal: ");

inorder(root);

printf("\n");

break;

case 5:

printf("Exiting program.\n");

exit(0);

default:

printf("Invalid choice. Try again.\n");

return 0;
}

Output :

--- Binary Search Tree Menu ---

1. Insert

2. Delete

3. Search

4. Inorder Traversal

5. Exit

Enter choice: 1

Enter value to insert: 2

--- Binary Search Tree Menu ---

1. Insert

2. Delete

3. Search

4. Inorder Traversal

5. Exit

Enter choice: 4

Inorder Traversal: 2
4.7 Threaded Binary Tree:
​
A threaded binary tree is a type of binary tree data structure where the empty left
and right child pointers in a binary tree are replaced with threads that link nodes
directly to their in-order predecessor or successor, thereby providing a way to
traverse the tree without using recursion or a stack.
There are two types of threaded binary trees.

●​ Single Threaded: Where a NULL right pointer is made to point to the

inorder successor (if successor exists)
●​ Double Threaded: Where both left, and right NULL pointers are made to
point to inorder predecessor and inorder successor respectively.

Advantages of Threaded Binary Tree

●​ In this Tree it enables linear traversal of elements.

●​ It eliminates the use of stack as it performs linear traversal, so save memory.
●​ Enables to find parent node without explicit use of parent pointer.
●​ Threaded trees give forward and backward traversal of nodes by in-order
fashion.

Disadvantages of Threaded Binary Tree

●​ Every node in threaded binary tree needs extra information (extra memory)
to indicate whether its left or right node indicated its child nodes or its
inorder predecessor or successor. So, the node consumes extra memory to
implement.
●​ Insertion and deletion are way more complex and time consuming than the
normal one since both threads and ordinary links need to be maintained.
●​ Implementing threads for every possible node is complicated.

4.8 Expression Tree:

The expression tree is a binary tree in which each internal node corresponds to the
operator and each leaf node corresponds to the operand so for example expression
tree for 3 + ((5+9) *2) would be:
Construction of Expression Tree:
Now for constructing an expression tree we use a stack. We loop through input
expression and do the following for every character.
1.​ If a character is an operand push that into the stack
2.​ If a character is an operator pop two values from the stack, make them its
child and push the current node again.
In the end, the only element of the stack will be the root of an expression tree.

Building Expression tree from Prefix Expression:​

Given a character array a[] represents a prefix expression. The task is to build an
Expression Tree for the expression and then print the infix and postfix expression
of the built tree.

a[]= “*+ab-cd”

Approach: If the character is an operand i.e. X then it’ll be the leaf node of the
required tree as all the operands are at the leaf in an expression tree. Else if the
character is an operator and of the form OP X Y then it’ll be an internal node with
left child as the expression Tree(X) and right child as the expression Tree(Y) which
can be solved using a recursive function.

Building Expression tree from Postfix Expression:

Here is how our algorithm would handle 5 2 + 3 1- *:

4.9 Heap: A Heap is a special Tree-based Data Structure that has the
following properties.
●​ It is a Complete Binary Tree.
●​ It either follows max heap or min heap property.
Max-Heap: The value of the root node must be the greatest among all its
descendant nodes and the same thing must be done for its left and right
sub-tree also.
Min-Heap: The value of the root node must be the smallest among all its
descendant nodes and the same thing must be done for its left and right
sub-tree also.
Properties of Heap:

●​ The minimum or maximum element is always at the root of the heap,

allowing constant-time access.
●​ The relationship between a parent node at index ‘i’ and its children is given
by the formulas: left child at index 2i+1 and right child at index 2i+2 for
0-based indexing of node numbers.
●​ As the tree is complete binary, all levels are filled except possibly the last
level. And the last level is filled from left to right.
●​ When we insert an item, we insert it at the last available slot and then
rearrange the nodes so that the heap property is maintained.
●​ When we remove an item, we swap root with the last node to make sure
either the max or min item is removed. Then we rearrange the remaining
nodes to ensure heap property (max or min)

Operations Supported by Heap:

Heapify: It is the process to rearrange the elements to maintain the property of

heap data structure. It is done when root is removed (we replace root with the last
node and then call heapify to ensure that heap property is maintained) or heap is
built (we call heapify from the last internal node to root) to make sure that the heap
property is maintained.

●​ For max-heap, it makes sure the maximum element is the root of that binary
tree and all descendants also follow the same property.
●​ For min-heap, it balances in such a way that the minimum element is the
root and all descendants also follow the same property.

4.9.1 Insertion: When a new element is inserted into the heap, it can disrupt
the heap’s properties. To restore and maintain the heap structure, a heapify
operation is performed. This operation ensures the heap properties are preserved
Examples:

4.9.2 Deletion: If we delete the element from the heap, it always deletes the
root element of the tree and replaces it with the last element of the tree. Since we
delete the root element from the heap it will distort the properties of the heap, so
we need to perform heapify operations so that it maintains the property of the heap.

Example:

Question bank
1.​ What is a Binary Tree? Explain its properties.
2.​ Define Strictly Binary Tree and Complete Binary Tree with examples.
3.​ How is a binary tree represented in memory? Explain with an example.
4.​ Explain binary tree traversals (Inorder, Preorder, Postorder) with an
example.
5.​ Write a C program to implement Preorder traversal of a binary tree.
6.​ What is a Binary Search Tree (BST)? Explain its properties.
7.​ Write the algorithm for inserting an element into a Binary Search Tree
(BST).
8.​ Write the algorithm for deleting a node from a Binary Search Tree (BST).
9.​ What is a Threaded Binary Tree? Explain its advantages.
10.​Define Expression Tree. How is it useful in expression evaluation?
11.​Write a C program to insert a node into a Binary Search Tree (BST).
12.​Implement a C program to perform Inorder, Preorder, and Postorder traversal
of a binary tree.
13.​Write a C program to delete a node from a Binary Search Tree (BST).
14.​Explain the construction of an expression tree from a prefix and postfix
expression with an example.
15.​Write a C program to construct an Expression Tree from a given postfix
expression.
16.​What is a Heap Tree? Explain Min Heap and Max Heap with examples.
17.​Write a C program to create a Heap Tree using an array.
18.​Explain Insertion in a Heap and write the algorithm for inserting an element
into a heap.
19.​Write a C program to insert an element into a Max Heap and maintain heap
properties.
20.​Explain Deletion from a Heap and write an algorithm for deleting an
element from a heap.
21.​Write a C program to construct and traverse a Binary Tree using recursion.
22.​Implement a C program to insert, delete, and search elements in a Binary
Search Tree (BST).
23.​Write a C program to convert a prefix and postfix expression into an
Expression Tree and evaluate it.
24.​Implement a C program to create and traverse a Threaded Binary Tree.
25.​Write a C program to insert an element into a Heap Tree and maintain the
heap structure.
26.​Implement a C program to delete the root node from a Heap Tree and restore
heap properties.
27.​Explain Heap Sort with an example. Implement Heap Sort in C.
28.​Implement a C program to perform Level Order Traversal of a binary tree
using a queue.
29.​Compare Binary Search Tree, Heap Tree, and Threaded Binary Tree based
on their properties and applications.
30.​Write a C program to implement a priority queue using a heap.

C programs:
●​ Write a C program to create a binary tree using dynamic memory allocation.
●​ Implement a C program to traverse a binary tree using Preorder Traversal.
●​ Write a C program to traverse a binary tree using Inorder Traversal.
●​ Implement a C program to traverse a binary tree using Postorder Traversal.
●​ Write a C program to check if a given binary tree is a Strictly Binary Tree.
●​ Implement a C program to check if a given binary tree is a Complete Binary
Tree.
●​ Write a C program to insert a node into a Binary Search Tree (BST).
●​ Implement a C program to search for a given key in a Binary Search Tree
(BST).
●​ Write a C program to represent a Binary Tree in memory using linked
representation.
●​ Implement a C program to construct an Expression Tree from a Postfix
Expression.
●​ Write a C program to construct and display a Binary Search Tree (BST).
●​ Implement a C program to delete a node from a Binary Search Tree (BST).
●​ Write a C program to check whether a given binary tree is Balanced or Not.
●​ Implement a C program to construct an Expression Tree from a Prefix
Expression.
●​ Write a C program to evaluate a Postfix Expression using an Expression
Tree.
●​ Implement a C program to create a Threaded Binary Tree and perform
Inorder traversal.
●​ Write a C program to create a Heap Tree and insert elements into it.
●​ Implement a C program to delete an element from a Max Heap.
●​ Write a C program to implement a Min Heap and perform insertion and
deletion operations.
●​ Implement a C program to convert a BST into a Balanced BST.
●​ Write a C program to implement all three tree traversals (Inorder, Preorder,
Postorder) in a Binary Tree.
●​ Implement a C program to insert, delete, and search elements in a Binary
Search Tree (BST).
●​ Write a C program to construct and evaluate an Expression Tree from a
Postfix Expression.
●​ Implement a C program to construct and evaluate an Expression Tree from a
Prefix Expression.
●​ Write a C program to implement a Threaded Binary Tree and perform
traversal without recursion.
●​ Implement a C program to create a Heap Tree, insert elements, and maintain
heap properties.
●​ Write a C program to delete the root node from a Heap Tree and restructure
the heap.
●​ Implement a C program for Heap Sort using a Min Heap or Max Heap.
●​ Write a C program to convert a Binary Tree into its Mirror Image.
●​ Implement a C program to find the Lowest Common Ancestor (LCA) of two
nodes in a Binary Search Tree.