Binary Tree: Given two trees, check if the structure are identical

Problem Statement:

You are given two trees, you need to check if both tree structure are identical

Example:

Input:

Output: Yes

Solution Explanation:

For the solution, we traverse both the trees node by node and check if the same path exists.

We do not need to check the values, we need to check for the structure.

If yes, return true else false

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}


int solution(Node* a, Node* b)
{

    if (a==NULL && b==NULL)
        return 1;

    if (a!=NULL && b!=NULL)
    {
        return
        (
            solution(a->left, b->left) && solution(a->right, b->right)
        );
    }

    return 0;
} 

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root_1 = newNode(10);
    root_1->left = newNode(8);
    root_1->right = newNode(12);
    root_1->left->left = newNode(2);
    root_1->left->right = newNode(9);
    root_1->right->left = newNode(11);
    root_1->right->right = newNode(14);

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root_2 = newNode(10);
    root_2->left = newNode(8);
    root_2->right = newNode(12);
    root_2->left->left = newNode(2);
    root_2->left->right = newNode(9);
    root_2->right->left = newNode(11);
    root_2->right->right = newNode(14);

    cout<< solution(root_1, root_2);

    return 0;
}

Output

1