Determine if two trees are same in C++ – LeetCode Solution [Easy]

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and each identical node has the same value.

Problem statement: https://leetcode.com/problems/same-tree/

Binary Trees

Pseudocode

1. Traverse the given binary trees rooted at root(p) and root(q) in a preorder fashion.
2. Do if p == NULL && q == NULL, return true
3. Else if either of the two is null not both, 
     ie p == NULL || q == NULL, return false
3. Traverse p->left && p->right and q->left && q->right
4. If info[p] and info[q] for (p and q) and also for (p->left and q->left) and (p->right and q->right) match equal respectively, return true
5. Else, return false 

Code Implementation

//
//  main.cpp
//  Same Tree
//
//  Created by Himanshu on 14/10/21.
//


#include <iostream>
#include <queue>
using namespace std;

struct node {
    int info = 0;
    struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data)
{
    node* Node = new node();
    Node->info = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}

bool checkIfSame(Node *p, Node *q) {
    if (p == NULL && q == NULL) {
        return true;
    } else if (p == NULL || q == NULL) {
        return false;
    }
    if (p->info == q->info && checkIfSame(p->left, q->left) &&
        checkIfSame(p->right, q->right)) {
        return true;
    } else {
        return false;
    }
        
}


int main() {
    Node *root = newNode(21);
    root->left = newNode(30);
    root->right = newNode(31);
    root->right->left = newNode(40);
    root->right->left->right = newNode(51);
    
    Node *root1 = newNode(21);
    root1->left = newNode(30);
    root1->right = newNode(31);
    root1->right->left = newNode(40);
    root1->right->left->right = newNode(51);
    
    Node *root2 = newNode(21);
    root2->left = newNode(30);
    root2->right = newNode(31);
    root2->right->left = newNode(40);
    root2->right->left->right = newNode(50);

    cout<<"Are trees with root (root) and root (root1) are same?"<<endl;
    if (checkIfSame(root, root1)) {
        cout<<"Trees are same"<<endl;
    } else {
        cout<<"Trees are not same"<<endl;
    }
    
    cout<<"Are trees with root (root) and root (root2) are same?"<<endl;
    if (checkIfSame(root, root2)) {
        cout<<"Trees are same"<<endl;
    } else {
        cout<<"Trees are not same"<<endl;
    }

    return 0;
}


Output

Are trees with root (root) and root (root1) are same?
Trees are same
Are trees with root (root) and root (root2) are same?
Trees are not same

Time complexity: O(n) where n is the number of nodes in larger tree.

Here’s a working example:

https://ideone.com/zB1xEH

Leave a Reply

Your email address will not be published.