Sign in

Search

Unknown user
ADS ASSIGNMENT
Hariharasudhann
Hariharasudhann
3 min read
·
Apr 6, 2026

Listen

Share

1)Check if binary tree is a Heap

What does it mean: “Binary Tree is a Heap”?

A Binary Heap must satisfy TWO conditions:

-) Complete Binary Tree property

*)Tree should be filled level by level

*)Left to right filling (no gaps in between)

->Except the last level, all levels must be completely full.

-) Heap Order property

There are two types:

*)Max Heap

Root has the minimum value

Parent ≥ Children

*)Min Heap

Parent ≤ Children

Root has the minimum value

2) To print all leaf node:

Logic:

If node.left == NULL AND node.right == NULL

Then it is a leaf

Pseudo code:

if node is NULL: return

if node.left == NULL and node.right == NULL:

print node

else:

traverse left

3) what is heap sort?

Heap Sort is a comparison-based sorting algorithm that uses a special data structure called a Heap.

-)In practice, we usually use a Max Heap for sorting in ascending order.

What is a Max Heap?
It is a complete binary tree
Parent ≥ children
The largest element is always at the root
Step 1: Build a Max Heap
After arranging the array as a max heap

Array form:

10,5,3,4,1

Step 2: Swap Root with Last Element
Root (largest) = 10
Swap it with last element (1)
codeCopy code

1,5,3,4,10

Now 10 is fixed at the correct position

Step 3: Heapify the Remaining Elements

Heapify the first 4 elements:

Array:

5,4,3,1,10

Step 4: Repeat
Swap 5 with 1
Heapify remaining
Continue until sorted
Final sorted array:

1,3,5,4,10

PROGRAM:

#include<iostream>
using namespace std;
class node{
public:
int data;
node*left,*right;
node(int val){
data=val;
left=right=NULL;
}
};
node*insert(node*root,int v){
if(root==NULL){
return new node(v);
}
if(v<root->data){
root->left=insert(root->left,v);
}else{
root->right=insert(root->right,v);}
return root;}
int lca(node*root,int a,int b){
if(a<root->data && b<root->data){
return lca(root->left,a,b);
}if(a>root->data && b>root->data){
return lca(root->right,a,b);}
return root->data;}
int main(){
node*t=NULL;
t=insert(t,11);
t=insert(t,7);
t=insert(t,6);
t=insert(t,10);
t=insert(t,24);
t=insert(t,19);
t=insert(t,35);
int a,b;
cout<<”Enter Two Numbers:”;
cin>>a>>b;
int c=lca(t,a,b);
cout<<”Ancestors of The Number Is: “<<c;
return 0;}

INPUT/OUTPUT:

EXPLANATION:

This program creates a Binary Search Tree (BST) and inserts values into it using the insert() function. It then finds the Lowest Common Ancestor (LCA) of two given nodes using BST properties. Finally, it takes two numbers from the user and prints their common ancestor in the tree.

2) Adding one two all the nodes of bst

PROGRAM:

#include<iostream>
using namespace std;
class node{
public:
int data;
node*left,*right;
node(int val){
data=val;
left=right=NULL;
}
};
node*insert(node*root,int v){
if(root==NULL){
return new node(v);
}
if(v<root->data){
root->left=insert(root->left,v);
}else{
root->right=insert(root->right,v);
}
return root;
}
void addone(node*root){
if(root==NULL){
return;
}
addone(root->left);
root->data=root->data+1;
cout<<root->data<<” “;
addone(root->right);
}
int main(){
node*t=NULL;
t=insert(t,11);
t=insert(t,7);
t=insert(t,6);
t=insert(t,10);
t=insert(t,24);
t=insert(t,19);
t=insert(t,35);
cout<<”NODES:\n”;
addone(t);
return 0;
}
INPUT/OUTPUT:

EXPLANATION:

This program builds a Binary Search Tree (BST) by inserting several values using the insert() function.The addone() function performs an inorder traversal, increases each node’s value by 1, and prints the updated values. Thus, it outputs the tree elements in sorted order after adding one to every node.

3) Given the rootof a binary tree, return the inorder traversal of its node values.

PROGRAM:

#include<iostream>
using namespace std;
class node{
public:
int data;
node*left,*right;
node(int val){
data=val;
left=right=NULL;}};
node*insert(node*root,int v){
if(root==NULL){
return new node(v);
}
if(v<root->data){
root->left=insert(root->left,v);
}else{
root->right=insert(root->right,v);
}
return root;
}
void inorder(node*root){
if(root==NULL){
return;
}
inorder(root->left);
cout<<root->data<<” “;
inorder(root->right);
}
int main(){
node*t=NULL;
t=insert(t,11);
t=insert(t,7);
t=insert(t,6);
t=insert(t,10);
t=insert(t,24);
t=insert(t,19);
t=insert(t,35);
cout<<”Inorder Traversal:\n”;
inorder(t);
return 0;
}

INPUT/OUTPUT:

4) Insert a value into a BST and return the updated root.

PROGRAM:

#include <iostream>
using namespace std;
struct node {
int data;
node* left;
node* right;
node(int value) {
data = value;
left = right = NULL;
}
};
node* insert(node* root, int v) {
if (root == NULL) {
return new node(v);
}
if (v < root->data) {
root->left = insert(root->left, v);
}
else {
root->right = insert(root->right, v);
}
return root;
}
void inorder(node* root) {
if (root == NULL) return;
inorder(root->left);
cout << root->data << “ “;
inorder(root->right);
}
int main() {
node* root = NULL;
root =insert(root,11);
insert(root,7);
insert(root,6);
insert(root,10);
insert(root,24);
insert(root,19);
insert(root,35);
inorder(root);
return 0;
}
INPUT/OUTPUT:

EXPLANATION:

This program creates a Binary Search Tree (BST) using a struct node and inserts multiple values into it.The insert() function places each value in the correct position based on BST rules.The inorder() function prints the tree elements in sorted ascending order.

5) To search for element

PROGRAM:

#include <iostream>
using namespace std;
class BTreeNode {
public:
int keys[2];
BTreeNode* child[3];
int n;
bool leaf;
BTreeNode(bool isLeaf) {
leaf = isLeaf;
n = 0;
for (int i = 0; i < 3; i++)
child[i] = NULL;
}
void traverse() {
int i;
for (i = 0; i < n; i++) {
if (!leaf)
child[i]->traverse();
cout << keys[i] << “ “;
}
if (!leaf)
child[i]->traverse();
}
BTreeNode* search(int k) {
int i = 0;
while (i < n && k > keys[i])
i++;
if (i < n && keys[i] == k)
return this;
if (leaf)
return NULL;
return child[i]->search(k);
}
void insertNonFull(int k);
void splitChild(int i, BTreeNode* y);
};
class BTree {
public:
BTreeNode* root;
BTree() {
root = NULL;
}
void insert(int k);
BTreeNode* search(int k) {
if (root == NULL)
return NULL;
return root->search(k);
}
};
void BTreeNode::insertNonFull(int k) {
int i = n — 1;
if (leaf) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i — ;
}
keys[i + 1] = k;
n++;
} else {
while (i >= 0 && keys[i] > k)
i — ;
if (child[i + 1]->n == 2) {
splitChild(i + 1, child[i + 1]);
if (keys[i + 1] < k)
i++;
}
child[i + 1]->insertNonFull(k);
}
}
void BTreeNode::splitChild(int i, BTreeNode* y) {
BTreeNode* z = new BTreeNode(y->leaf);
z->n = 1;
z->keys[0] = y->keys[1];
if (!y->leaf) {
z->child[0] = y->child[1];
z->child[1] = y->child[2];
}
y->n = 1;
for (int j = n; j >= i + 1; j — )
child[j + 1] = child[j];
child[i + 1] = z;
for (int j = n — 1; j >= i; j — )
keys[j + 1] = keys[j];
keys[i] = y->keys[0];
n++;
}
void BTree::insert(int k) {
if (root == NULL) {
root = new BTreeNode(true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2) {
BTreeNode* s = new BTreeNode(false);
s->child[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->child[i]->insertNonFull(k);
root = s;
} else {
root->insertNonFull(k);
}
}
}
int main() {
BTree t;
int keys[] = {10, 20, 5, 6, 12, 30, 7, 17};
for (int i = 0; i < 8; i++)
t.insert(keys[i]);
int searchKey = 30;
if (t.search(searchKey))
cout <<searchKey<< “ Found”;
else
cout << “Not Found”;
return 0;
}
INPUT/OUPUT:

30

EXPLANATION:

This program implements a B-Tree of order 3 where each node can store up to two keys and three children. It supports insertion with node splitting (splitChild) to maintain balance and efficient searching.After inserting values, it searches for a key and prints whether it is found in the B-Tree.

6)Check whether a tree is valid BST

PROGRAM:

#include <iostream>
#include <climits>
using namespace std;
struct Node {
int val;
Node* left;
Node* right;

Node(int x) {
val = x;
left = right = NULL;
}
};
bool validate(Node* root, long minVal, long maxVal) {

if (!root) return true;

if (root->val <= minVal || root->val >= maxVal)
return false;

return validate(root->left, minVal, root->val) &&
validate(root->right, root->val, maxVal);
}

int main() {
Node* root = new Node(5);
root->left = new Node(1);
root->right = new Node(4);
root->right->left = new Node(3);
root->right->right = new Node(6);

if (validate(root, LONG_MIN, LONG_MAX))
cout << “Valid BST”;
else
cout << “Not a Valid BST”;

return 0;
}
INPUT/OUTPUT:

EXPLANATION:

This program checks whether a binary tree satisfies the Binary Search Tree (BST) property.The validate() function ensures every node value lies within a valid min–max range recursively.It prints whether the given tree structure is a valid BST or not.

7)Given an unbalanced BST, convert it into a balanced BST.

PROGRAM:

#include <iostream>
#include <vector>
using namespace std;
struct Node {
int val;
Node* left;
Node* right;

Node(int x) {
val = x;
left = right = NULL;
}
};
void inorderStore(Node* root, vector<int>& arr) {
if (!root) return;

inorderStore(root->left, arr);
arr.push_back(root->val);
inorderStore(root->right, arr);
}
Node* buildBalanced(vector<int>& arr, int start, int end) {
if (start > end) return NULL;

int mid = (start + end) / 2;
Node* root = new Node(arr[mid]);

root->left = buildBalanced(arr, start, mid — 1);
root->right = buildBalanced(arr, mid + 1, end);

return root;
}
void inorderPrint(Node* root) {
if (!root) return;
inorderPrint(root->left);
cout << root->val << “ “;
inorderPrint(root->right);
}
int main() {
Node* root = new Node(1);
root->right = new Node(2);
root->right->right = new Node(3);
root->right->right->right = new Node(4);
vector<int> arr;
inorderStore(root, arr);
Node* balancedRoot = buildBalanced(arr, 0, arr.size() — 1);
cout << “Balanced BST Inorder: “;
inorderPrint(balancedRoot);
return 0;
}
INPUT/OUTPUT:

EXPLANATION:

This program converts an unbalanced BST into a balanced BST.
It first stores the tree values using inorder traversal (sorted order), then rebuilds the tree using the middle element to maintain balance.
Finally, it prints the inorder traversal of the balanced tree.

8) To add and search word:

PROGRAM:

#include <iostream>
using namespace std;
class TrieNode {
public:
TrieNode* children[26];
bool isEnd;
TrieNode() {
isEnd = false;
for (int i = 0; i < 26; i++)
children[i] = NULL;
}
};
class WordDictionary {
private:
TrieNode* root;
bool searchHelper(string word, int index, TrieNode* node) {
if (!node) return false;
if (index == word.length())
return node->isEnd;
char c = word[index];
if (c == ‘.’) {
for (int i = 0; i < 26; i++) {
if (searchHelper(word, index + 1, node->children[i]))
return true;
}
return false;
} else {
return searchHelper(word, index + 1,
node->children[c — ‘a’]);
}
}
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* node = root;
for (int i = 0; i < word.length(); i++) {
int index = word[i] — ‘a’;
if (!node->children[index])
node->children[index] = new TrieNode();
node = node->children[index];
}
node->isEnd = true;
}
bool search(string word) {
return searchHelper(word, 0, root);
}
};
int main() {
WordDictionary obj;
obj.addWord(“bad”);
obj.addWord(“dad”);
obj.addWord(“mad”);
cout << obj.search(“pad”) << endl;
cout << obj.search(“bad”) << endl;
cout << obj.search(“.ad”) << endl;
cout << obj.search(“b..”) << endl;
return 0;
}
INPUT/OUTPUT:

EXPLANATION:

This program implements a Trie (Prefix Tree) to store and search words efficiently. It supports adding words and searching with a wildcard . that can match any character using recursion.The main function demonstrates normal search and pattern-based search using the Trie structure.