ASSIGNMENT 2

1. Read n ints and make a binary search tree (BST). Do k search operations to print results as y/n.
Input: (n, x_i, k, y_i)
4
2 1 4 3
3
3 7 1
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

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

Node* createNode(int data) {

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

Node* insert(Node* root, int data) {

if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}

int search(Node* root, int key) {

if (root == NULL) return 0;
if (root->data == key) return 1;
return key < root->data ? search(root->left, key) : search(root->right, key);
}

int main() {
int n, k, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d", &k);
for (int i = 0; i < k; i++) {
scanf("%d", &val);
printf(search(root, val) ? "y " : "n ");
}
return 0;
}

2. Read n ints and make a BST in the same order. Print the tree in preorder, inorder and postorder
traversals. Separate characters by
Input: (n, x_i)
4
2143

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
 struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void preorder(Node* root) {
if (root) {
printf("%d_", root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d_", root->data);
inorder(root->right);
}
}
void postorder(Node* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d_", root->data);
}
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
preorder(root);
printf("\n");
inorder(root);
printf("\n");
postorder(root);
printf("\n");
return 0;
}

3. Read 2n ints. Use each half to create two BSTs in the given order. Find if the two trees are identical.
Print y/n. There are T test cases.
Input: (T, n, x_i)
3
3
123132
123231
213231
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *left, *right;
} Node;
Node *createNode(int data)
{
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node *insert(Node *root, int data)
{
if (root == NULL)
return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}
int areIdentical(Node *root1, Node *root2)
{
if (!root1 && !root2)
return 1;
if (!root1 || !root2)
return 0;
return (root1->data == root2->data) &&
areIdentical(root1->left, root2->left) &&
areIdentical(root1->right, root2->right);
}
int main()
{
int T, n, val;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
Node *root1 = NULL, *root2 = NULL;
for (int i = 0; i < n; i++)
{
scanf("%d", &val);
root1 = insert(root1, val);
}
for (int i = 0; i < n; i++)
{
scanf("%d", &val);
root2 = insert(root2, val);
}
printf(areIdentical(root1, root2) ? "y\n" : "n\n");
}
return 0;
}

4. Given a BST, print out all root-to-leaf paths.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void printPaths(Node* root, int path[], int pathLen) {
if (root == NULL) return;
path[pathLen] = root->data;
pathLen++;
if (root->left == NULL && root->right == NULL) {
for (int i = 0; i < pathLen; i++) {
printf("%d ", path[i]);
}
printf("\n");
} else {
printPaths(root->left, path, pathLen);
printPaths(root->right, path, pathLen);
}
}
void printRootToLeafPaths(Node* root) {
int path[1000];
printPaths(root, path, 0);
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printRootToLeafPaths(root);
return 0;
}

5. Find the number of leaves in a BST.

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

typedef struct Node {

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

Node* createNode(int data) {

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

Node* insert(Node* root, int data) {

if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
int countLeaves(Node* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}

int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf("%d\n", countLeaves(root));
return 0;
}

[Link] sum of all the leaf nodes in a BST.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
int sumLeafNodes(Node* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return root->data;
return sumLeafNodes(root->left) + sumLeafNodes(root->right);
}

int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf("%d\n", sumLeafNodes(root));
return 0;
}

7. Construct a binary tree given inorder and post-order traversal outputs.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
int search(int arr[], int start, int end, int value) {
for (int i = start; i <= end; i++) {
if (arr[i] == value) return i;
}
return -1;
}
Node* buildTree(int inorder[], int postorder[], int* postIndex, int inStart, int inEnd) {
if (inStart > inEnd) return NULL;
Node* node = createNode(postorder[*postIndex]);
(*postIndex)--;
if (inStart == inEnd) return node;
int inIndex = search(inorder, inStart, inEnd, node->data);
node->right = buildTree(inorder, postorder, postIndex, inIndex + 1, inEnd);
node->left = buildTree(inorder, postorder, postIndex, inStart, inIndex - 1);
return node;
}
void preorder(Node* root) {
if (root) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
int main() {
int n;
scanf("%d", &n);
int inorder[n], postorder[n];
for (int i = 0; i < n; i++) scanf("%d", &inorder[i]);
for (int i = 0; i < n; i++) scanf("%d", &postorder[i]);
int postIndex = n - 1;
Node* root = buildTree(inorder, postorder, &postIndex, 0, n - 1);
preorder(root);
printf("\n");
return 0;
}

8. Construct a full binary tree from given pre-order and post-order traversals and print in-order traversal
of it.
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

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

Node* createNode(int data) {

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

Node* buildFullTree(int pre[], int post[], int* preIndex, int l, int h, int size) {
if (*preIndex >= size || l > h) return NULL;
 Node* root = createNode(pre[*preIndex]);
(*preIndex)++;
if (l == h) return root;
int i;
for (i = l; i <= h; i++) {
if (post[i] == pre[*preIndex]) break;
}
if (i <= h) {
root->left = buildFullTree(pre, post, preIndex, l, i, size);
root->right = buildFullTree(pre, post, preIndex, i + 1, h - 1, size);
}
return root;
}

void inorder(Node* root) {

if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

int main() {
int n;
scanf("%d", &n);
int pre[n], post[n];
for (int i = 0; i < n; i++) scanf("%d", &pre[i]);
for (int i = 0; i < n; i++) scanf("%d", &post[i]);
int preIndex = 0;
Node* root = buildFullTree(pre, post, &preIndex, 0, n - 1, n);
inorder(root);
printf("\n");
return 0;
}

9. Delete a BST. Print the order in which nodes are deleted.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void deleteBST(Node* root) {
if (root == NULL) return;
deleteBST(root->left);
deleteBST(root->right);
printf("%d ", root->data);
free(root);
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
deleteBST(root);
printf("\n");
return 0;
}

10. Construct the mirror tree of a given BST.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void mirror(Node* root) {
if (root == NULL) return;
Node* temp = root->left;
root->left = root->right;
root->right = temp;
mirror(root->left);
mirror(root->right);
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
mirror(root);
inorder(root);
printf("\n");
return 0;
}

11. Given a Binary Search Tree, and an integer k. Print all the nodes which are at k distance from root.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void printKDistanceNodes(Node* root, int k) {
if (root == NULL) return;
if (k == 0) {
printf("%d ", root->data);
return;
}
printKDistanceNodes(root->left, k - 1);
printKDistanceNodes(root->right, k - 1);
}
int main() {
int n, k, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d", &k);
printKDistanceNodes(root, k);
printf(“\n");
return 0;
}

12. Find out the in-order successor and predecessor of a given node in a BST.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
 else root->right = insert(root->right, data);
return root;
}
void ndPreSuc(Node* root, Node** pre, Node** suc, int key) {
if (root == NULL) return;
if (root->data == key) {
if (root->left) {
Node* temp = root->left;
while (temp->right) temp = temp->right;
*pre = temp;
}
if (root->right) {
Node* temp = root->right;
while (temp->left) temp = temp->left;
*suc = temp;
}
return;
}
if (root->data > key) {
*suc = root;
ndPreSuc(root->left, pre, suc, key);
} else {
*pre = root;
ndPreSuc(root->right, pre, suc, key);
}
}
int main() {
int n, key, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d", &key);
Node *pre = NULL, *suc = NULL;
ndPreSuc(root, &pre, &suc, key);
if (pre) printf("Predecessor: %d\n", pre->data);
else printf("Predecessor: None\n");
if (suc) printf("Successor: %d\n", suc->data);
else printf("Successor: None\n”);
return 0;
}

13. Given a BST and a key, write a function that prints all the ancestors of the key in the given binary tree.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
fi
fi
fi
fi
 else root->right = insert(root->right, data);
return root;
}
void ndPreSuc(Node* root, Node** pre, Node** suc, int key) {
if (root == NULL) return;
if (root->data == key) {
if (root->left) {
Node* temp = root->left;
while (temp->right) temp = temp->right;
*pre = temp;
}
if (root->right) {
Node* temp = root->right;
while (temp->left) temp = temp->left;
*suc = temp;
}
return;
}
if (root->data > key) {
*suc = root;
ndPreSuc(root->left, pre, suc, key);
} else {
*pre = root;
ndPreSuc(root->right, pre, suc, key);
}
}
int ndAncestors(Node* root, int key) {
if (root == NULL) return 0;
if (root->data == key) return 1;
if ( ndAncestors(root->left, key) || ndAncestors(root->right, key)) {
printf("%d ", root->data);
return 1;
}
return 0;
}
int main() {
int n, key, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d", &key);
Node *pre = NULL, *suc = NULL;
ndPreSuc(root, &pre, &suc, key);
if (pre) printf("Predecessor: %d\n", pre->data);
else printf("Predecessor: None\n");
if (suc) printf("Successor: %d\n", suc->data);
else printf("Successor: None\n");
printf("Ancestors: ");
ndAncestors(root, key);
printf("\n");
return 0;
}

14. Write a function which deletes all the terminal nodes in BST.
#include <stdio.h>
#include <stdlib.h>
fi
fi
fi
fi
fi
fi
fi
fi
 typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void ndPreSuc(Node* root, Node** pre, Node** suc, int key) {
if (root == NULL) return;
if (root->data == key) {
if (root->left) {
Node* temp = root->left;
while (temp->right) temp = temp->right;
*pre = temp;
}
if (root->right) {
Node* temp = root->right;
while (temp->left) temp = temp->left;
*suc = temp;
}
return;
}
if (root->data > key) {
*suc = root;
ndPreSuc(root->left, pre, suc, key);
} else {
*pre = root;
ndPreSuc(root->right, pre, suc, key);
}
}
int ndAncestors(Node* root, int key) {
if (root == NULL) return 0;
if (root->data == key) return 1;
if ( ndAncestors(root->left, key) || ndAncestors(root->right, key)) {
printf("%d ", root->data);
return 1;
}
return 0;
}
Node* deleteLeafNodes(Node* root) {
if (root == NULL) return NULL;
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
root->left = deleteLeafNodes(root->left);
root->right = deleteLeafNodes(root->right);
return root;
}
int main() {
int n, key, val;
fi
fi
fi
fi
fi
fi
 scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d", &key);
Node *pre = NULL, *suc = NULL;
ndPreSuc(root, &pre, &suc, key);
if (pre) printf("Predecessor: %d\n", pre->data);
else printf("Predecessor: None\n");
if (suc) printf("Successor: %d\n", suc->data);
else printf("Successor: None\n");
printf("Ancestors: ");
ndAncestors(root, key);
printf("\n");
root = deleteLeafNodes(root);
return 0;
}

15. Given a BST, delete all the nodes by repeated deletion of root. Print the inorder traversal after every
deletion.
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
Node* ndMin(Node* root) {
while (root->left) root = root->left;
return root;
}
Node* deleteRoot(Node* root) {
if (root == NULL) return NULL;
if (root->left == NULL) {
Node* temp = root->right;
printf("Deleted: %d\n", root->data);
free(root);
return temp;
}
fi
fi
fi
 if (root->right == NULL) {
Node* temp = root->left;
printf("Deleted: %d\n", root->data);
free(root);
return temp;
}
Node* temp = ndMin(root->right);
root->data = temp->data;
root->right = deleteRoot(root->right);
return root;
}
void deleteBST(Node* root) {
while (root) {
inorder(root);
printf("\n");
root = deleteRoot(root);
}
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
deleteBST(root);
return 0;
}

16. Given a binary tree, nd if it is a BST.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int isBSTUtil(Node* root, int min, int max) {
if (root == NULL) return 1;
if (root->data <= min || root->data >= max) return 0;
fi
fi
 return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}
int isBST(Node* root) {
return isBSTUtil(root, INT_MIN, INT_MAX);
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf(isBST(root) ? "Yes\n" : "No\n");
return 0;
}

17. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left
subtree and right subtree. Write a function that returns 1 if the given BST is SumTree and 0 otherwise. All
leaf nodes are trivial SumTrees.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int isBSTUtil(Node* root, int min, int max) {
if (root == NULL) return 1;
if (root->data <= min || root->data >= max) return 0;
return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}
int isBST(Node* root) {
return isBSTUtil(root, INT_MIN, INT_MAX);
}
int sum(Node* root) {
if (root == NULL) return 0;
return root->data + sum(root->left) + sum(root->right);
}
int isSumTree(Node* root) {
 if (root == NULL || (root->left == NULL && root->right == NULL)) return 1;
int leftSum = sum(root->left);
int rightSum = sum(root->right);
return (root->data == leftSum + rightSum) && isSumTree(root->left) && isSumTree(root->right);
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf(isBST(root) ? "Yes\n" : "No\n");
printf(isSumTree(root) ? "SumTree\n" : "Not SumTree\n");
return 0;
}

18. Find distance between two given keys of a BST. Distance between two nodes is the minimum number of
edges to be traversed to reach one node from other.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
Node* ndLCA(Node* root, int n1, int n2) {
if (root == NULL) return NULL;
if (root->data > n1 && root->data > n2)
return ndLCA(root->left, n1, n2);
if (root->data < n1 && root->data < n2)
return ndLCA(root->right, n1, n2);
return root;
}
int ndDistance(Node* root, int key) {
if (root == NULL) return -1;
int dist = 0;
while (root != NULL) {
if (key < root->data) root = root->left;
fi
fi
fi
fi
 else if (key > root->data) root = root->right;
else return dist;
dist++;
}
return -1;
}
int distanceBetweenNodes(Node* root, int n1, int n2) {
Node* lca = ndLCA(root, n1, n2);
int d1 = ndDistance(lca, n1);
int d2 = ndDistance(lca, n2);
return d1 + d2;
}
int main() {
int n, val, n1, n2;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d %d", &n1, &n2);
printf("Distance: %d\n", distanceBetweenNodes(root, n1, n2));
return 0;
}

19. Write a function to print all the nodes in a BST along with their individual heights and depths.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
Node* ndLCA(Node* root, int n1, int n2) {
if (root == NULL) return NULL;
if (root->data > n1 && root->data > n2)
return ndLCA(root->left, n1, n2);
if (root->data < n1 && root->data < n2)
return ndLCA(root->right, n1, n2);
return root;
fi
fi
fi
fi
fi
fi
 }
int ndDistance(Node* root, int key) {
if (root == NULL) return -1;
int dist = 0;
while (root != NULL) {
if (key < root->data) root = root->left;
else if (key > root->data) root = root->right;
else return dist;
dist++;
}
return -1;
}
int distanceBetweenNodes(Node* root, int n1, int n2) {
Node* lca = ndLCA(root, n1, n2);
int d1 = ndDistance(lca, n1);
int d2 = ndDistance(lca, n2);
return d1 + d2;
}
int height(Node* root) {
if (root == NULL) return -1;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
int depth(Node* root, int key, int level) {
if (root == NULL) return -1;
if (root->data == key) return level;
int left = depth(root->left, key, level + 1);
if (left != -1) return left;
return depth(root->right, key, level + 1);
}
void printNodesWithHeightAndDepth(Node* root, Node* originalRoot) {
if (root == NULL) return;
printNodesWithHeightAndDepth(root->left, originalRoot);
printf("Node: %d, Height: %d, Depth: %d\n", root->data, height(root), depth(originalRoot, root->data, 0));
printNodesWithHeightAndDepth(root->right, originalRoot);
}
int main() {
int n, val, n1, n2;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d %d", &n1, &n2);
printf("Distance: %d\n", distanceBetweenNodes(root, n1, n2));
printNodesWithHeightAndDepth(root, root);
return 0;
}

20. Print output of depth- rst search given a BST.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
fi
fi
fi
fi
fi
 Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void preorder(Node* root) {
if (root) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(Node* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
Node* ndLCA(Node* root, int n1, int n2) {
if (root == NULL) return NULL;
if (root->data > n1 && root->data > n2)
return ndLCA(root->left, n1, n2);
if (root->data < n1 && root->data < n2)
return ndLCA(root->right, n1, n2);
return root;
}
int ndDistance(Node* root, int key) {
if (root == NULL) return -1;
int dist = 0;
while (root != NULL) {
if (key < root->data) root = root->left;
else if (key > root->data) root = root->right;
else return dist;
dist++;
}
return -1;
}

int distanceBetweenNodes(Node* root, int n1, int n2) {

Node* lca = ndLCA(root, n1, n2);
int d1 = ndDistance(lca, n1);
int d2 = ndDistance(lca, n2);
return d1 + d2;
}
int height(Node* root) {
fi
fi
fi
fi
fi
fi
fi
 if (root == NULL) return -1;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
int depth(Node* root, int key, int level) {
if (root == NULL) return -1;
if (root->data == key) return level;
int left = depth(root->left, key, level + 1);
if (left != -1) return left;
return depth(root->right, key, level + 1);
}
void printNodesWithHeightAndDepth(Node* root, Node* originalRoot) {
if (root == NULL) return;
printNodesWithHeightAndDepth(root->left, originalRoot);
printf("Node: %d, Height: %d, Depth: %d\n", root->data, height(root), depth(originalRoot, root->data, 0));
printNodesWithHeightAndDepth(root->right, originalRoot);
}
int main() {
int n, val, n1, n2;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d %d", &n1, &n2);
printf("Distance: %d\n", distanceBetweenNodes(root, n1, n2));
printNodesWithHeightAndDepth(root, root);
printf("Preorder DFS: ");
preorder(root);
printf("\nPostorder DFS: ");
postorder(root);
printf("\n");
return 0;
}

21. Print output of breadth- rst search given a BST.

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

typedef struct Node {

int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
fi
 inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void preorder(Node* root) {
if (root) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(Node* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
void bfs(Node* root) {
if (root == NULL) return;
Node* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
Node* temp = queue[front++];
printf("%d ", temp->data);
if (temp->left) queue[rear++] = temp->left;
if (temp->right) queue[rear++] = temp->right;
}
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf("BFS: ");
bfs(root);
printf("\n");
return 0;
}

22. Remove all nodes which don’t lie in any path with sum>= k. A node can be a part of multiple paths. So
we have to delete it only in case when all paths from it have sum less than k. Print the in-order traversal
of the tree after truncation.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
 return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
Node* pruneTree(Node* root, int k, int pathSum) {
if (root == NULL) return NULL;
pathSum += root->data;
root->left = pruneTree(root->left, k, pathSum);
root->right = pruneTree(root->right, k, pathSum);
if (root->left == NULL && root->right == NULL && pathSum < k) {
free(root);
return NULL;
}
return root;
}
int main() {
int n, val, k;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
scanf("%d", &k);
root = pruneTree(root, k, 0);
inorder(root);
printf("\n");
return 0;
}

23. Delete all duplicates of a node from a given binary search tree.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else if (data > root->data) root->right = insert(root->right, data);
 return root;
}

void inorder(Node* root) {

if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
Node* ndMin(Node* root) {
while (root->left) root = root->left;
return root;
}
Node* deleteDuplicates(Node* root) {
if (root == NULL) return NULL;
root->left = deleteDuplicates(root->left);
root->right = deleteDuplicates(root->right);
if (root->left && root->data == root->left->data) {
Node* temp = root->left;
root->left = temp->left;
free(temp);
}
if (root->right && root->data == root->right->data) {
Node* temp = root->right;
root->right = temp->right;
free(temp);
}
return root;
}
int main() {
int n, val;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
root = deleteDuplicates(root);
inorder(root);
printf("\n");
return 0;
}
fi