Programs on Tree in Data Structure

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