## Program to Calculate the Difference Between the Sum of the Odd Level and Even Level Nodes of a Binary Tree

Code:

```#include<bits/stdc++.h>
using namespace std;

struct Node{
int val;
Node *left, *right;
};

Node* temp = new Node();
temp->val = value;
temp->left = temp->right = nullptr;
return temp;
}

int odd_even_difference(Node * root){
if(!root)return 0;
queue<Node*> q;
q.push(root);
int level = 0;
int even_sum = 0, odd_sum = 0;
while (!q.empty())
{
int sz = q.size();
level^=1;
while(sz--){
Node * current_node = q.front();
q.pop();
if(!level)even_sum+=current_node->val;
else odd_sum+=current_node->val;
if(current_node->left)q.push(current_node->left);
if(current_node->right)q.push(current_node->right);
}

}
return (odd_sum-even_sum);

}

int main(){
int ans = odd_even_difference(root);
cout<<"Difference is: "<<ans<<endl;
return 0;
}```

Output:

`Difference is: -11`

## Program to Convert Binary Tree to Binary Search Tree

Code:

```#include<bits/stdc++.h>
using namespace std;

struct Node{
int val;
Node *left,*right;
};

void addInorder(Node * node, int arr[], int * idx_ptr){
if(node == nullptr)return;
arr[*idx_ptr]=node->val;
(*idx_ptr)++;
}

int countNodes(Node * root){
if(root == nullptr)return 0;
return countNodes(root->left)  + countNodes(root->right)+1;
}

int compare(const void *a, const void* b){
return (*(int*)a - *(int*)b);
}

void arrayToBST(int * arr, Node * root, int *idx_ptr){
if(root == nullptr)return;
arrayToBST(arr, root->left, idx_ptr);
root->val= arr[*idx_ptr];
(*idx_ptr)++;
arrayToBST(arr, root->right, idx_ptr);
}
void convertToBST(Node * root){
if(root==nullptr)return;

int n = countNodes(root);
int *arr= new int[n];
int i = 0;

qsort(arr, n, sizeof(arr[0]), compare);
i = 0;
arrayToBST(arr, root, &i);
delete[] arr;
}

Node * newNode(int data){
struct Node* temp = new struct Node;
temp->val =data;
temp->right=temp->left= nullptr;
return temp;
}

void printInorder(Node * node){
if(node  == nullptr)return;

printInorder(node->left);
cout<<node->val<<" ";
printInorder(node->right);
}

int main()
{
Node * root = NULL;
root = newNode(10);
root->left = newNode(30);
root->right = newNode(15);
root->left->left = newNode(20);
root->right->right = newNode(5);
convertToBST(root);
printf("Following is the Inorder Traversal of the converted BST: \n");
printInorder(root);
}```

Output:

```Following is the Inorder Traversal of the converted BST:
5 10 15 20 30```

## Program to Determine Whether all Leaves are at Same Level

Code:

```#include<bits/stdc++.h>
using namespace std;

struct Node{
int val;
Node *left, *right;
};

Node * newNode(int value){
Node* temp = new Node;
temp->val = value;
temp->left=temp->right= nullptr;
return temp;
}

bool checkSameLevel(Node * root, int level  ,int *leafLevel){
if(root == nullptr)return true;
if(root->left == nullptr and root->right == nullptr){
if(*leafLevel ==0){
*leafLevel = level;
return true;
}
return (level == *leafLevel);
}
return checkSameLevel(root->left, level+1, leafLevel) and checkSameLevel(root->right, level+1, leafLevel);
}

bool check(Node * root){
int level = 0, leafLevel = 0;
return checkSameLevel(root, level, &leafLevel);
}
int main(){
struct Node *root = newNode(12);
root->left = newNode(5);
root->left->left = newNode(3);
root->left->right = newNode(9);
root->left->left->left = newNode(1);
root->left->left->left->right = newNode(1);
root->left->right->left = newNode(1);
if (check(root))
cout << "Leaves at same level.\n";
else
cout << "Leaves not at same level.\n";
return 0;
}```

Output:

`Leaves not at same level.`

## Program to Determine Whether two Trees are Identical

Code:

```#include <bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node *left;
Node *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->val = data;
temp->left = NULL;
temp->right = NULL;

return(temp);
}
bool isSameTree(Node *p, Node *q)
{
if (!q && !p)
return true;
if (!p || !q)
return false;
if (p->val != q->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

int main(){
Node *root1 = newNode(1);
Node *root2 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root2->left = newNode(2);
root2->right = newNode(3);
root2->left->left = newNode(4);
root2->left->right = newNode(5);
if(isSameTree(root1, root2))
cout << "Trees are identical.";
else
cout << "Trees are not identical.";
}```

Output:

`Trees are identical.`

## Program to Find Maximum Width of a Binary Tree

Code:

```#include <bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node *left;
Node *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->val = data;
temp->left = NULL;
temp->right = NULL;

return(temp);
}

int getMaxElement(Node* root)
{
if (root == NULL)return numeric_limits<int>::min();
int res = root->val;
int lres = getMaxElement(root->left);
int rres = getMaxElement(root->right);
res = max({rres,lres,res});
return res;
}

int main(){
Node *root1 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(94);
root1->left->right = newNode(5);
cout<<"Maximum element is: "<<getMaxElement(root1);
}```

Output:

`Maximum element is: 94`

## Program to Find the Largest Element in a Binary Tree

Code:

```#include <bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node *left;
Node *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->val = data;
temp->left = NULL;
temp->right = NULL;

return(temp);
}

bool searchBT(struct Node* node, int target)
{
if (node == NULL)
return false;
if (node->val == target)
return true;
bool res1 = searchBT(node->left, target);
if(res1) return true;

bool res2 = searchBT(node->right, target);
return res2;
}

int main(){
Node *root1 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(94);
root1->left->right = newNode(5);
cout<<"Largest element: "<<searchBT(root1,95);
}```

Output:

`Largest element: 0`

## Program to Find the Maximum Depth or Height of a Tree

Code:

```#include <bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node *left;
Node *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->val = data;
temp->left = NULL;
temp->right = NULL;

return(temp);
}

int maxDepth(Node* root) {
if(!root)return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
int main(){
Node *root1 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(94);
root1->left->right = newNode(5);
cout<<"Maximum depth of the tree is: ";
cout<<maxDepth(root1);
}```

Output:

`Maximum depth of the tree is: 3`

## Program to Find the Sum of all the Nodes of a Binary Tree

Code:

```#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
Node *left;
Node *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->val = data;
temp->left = NULL;
temp->right = NULL;
return(temp);
}

int sumAllNodes(Node* root)
{
if (root == NULL)
return 0;
return (root->val + sumAllNodes(root->left) + sumAllNodes(root->right));
}
int main(){
Node *root1 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(94);
root1->left->right = newNode(5);
cout<<"Sum of all nodes are: ";
cout<<sumAllNodes(root1);
}```

Output:

`Sum of all nodes are: 105`

## Program to Search a Node in a Binary Tree

Code:

```#include<bits/stdc++.h>
using namespace std;

struct Node{
int val;
Node *left, *right;
};

Node* temp = new Node();
temp->val = value;
temp->left = temp->right = nullptr;
return temp;
}

bool findNode(Node * root, int target){
if(root == nullptr) return false;
if(root->val == target) return true;
if(findNode(root->right, target))return true;
return findNode(root->left, target);

}

int main(){
`Node not found`