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* addNode(int value){ 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(){ Node* root = addNode(1); root->left = addNode(2); root->right = addNode(3); root->left->left = addNode(4); root->left->right = addNode(5); root->left->right->left = addNode(6); root->right->right = addNode(7); root->right->right->right = addNode(8); root->right->right->left = addNode(9); 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; addInorder(node->left, arr, idx_ptr); arr[*idx_ptr]=node->val; (*idx_ptr)++; addInorder(node->right, arr, 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; addInorder(root, arr, &i); 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* addNode(int value){ 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* root = addNode(1); root->left = addNode(2); root->right = addNode(3); root->left->left = addNode(4); root->left->right = addNode(5); root->left->right->left = addNode(6); root->right->right = addNode(7); root->right->right->right = addNode(8); root->right->right->left = addNode(9); int ans = findNode(root, 10); cout<<(ans?"Node found":"Node not found")<<endl; return 0; }
Output:
Node not found