Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Binary tree
1.2.
Problem Statement
1.3.
Some Examples
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Code in C++
2.2.1.
Complexity Analysis 
3.
Optimized Approach
3.1.
Algorithm
3.2.
Code in C++
3.2.1.
Complexity Analysis
4.
Frequently asked questions
4.1.
How do you know if a binary tree is complete?
4.2.
What is preorder traversal in a binary tree?
4.3.
What is a skewed binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if the leaf traversal of two Binary Trees is same?

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

The binary tree is one of the favorite topics of companies. Many companies like Amazon, Google, and Meta ask questions about the binary trees in interviews. So if companies are giving so much weightage to this topic, then this topic becomes important from the perspective of preparation for interviews.

To help you solve problems on binary trees, we will be discussing a simple problem of binary trees. This problem is to check if the leaf traversal of two binary trees is same or not?

Binary tree

A binary tree is a tree data structure in which each node has at most two children, which are known as the left and right children.

Each node in a binary tree has a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the tree's topmost node. The left and right pointers point to smaller "subtrees" on either side. A null pointer symbolizes the empty tree, a binary tree with no children.

Problem Statement

Ninjas have two binary trees. Both of the trees have n nodes. He gave both trees to you. He said he wanted to check whether the leaf traversal of the binary trees is the same or not? But, the problem is that he cannot check it by himself as he is busy with some other work. Can you help him with the problem?

You need to output 1 if the leaf traversals of both the trees are same and 0 if the leaf traversal of both the trees are not same. 

Before deep-diving into the solution to this problem, we should look at some examples to help us understand the problem better. 

Some Examples

Input 1:

Tree1: 


 

Tree2:


 

Output 1: 

1 

 

Explanation:

Leaf Traversal for Tree1 is {2, 3, 7}

Leaf Traversal for Tree2 is {2, 3, 7}

Since both traversals are the same, therefore, the output is 1.
 

Input 2:

Tree1:

Tree2:

Output:

1

 

Explanation:

Leaf Traversal for Tree1 is {9, 1}

Leaf Traversal for Tree2 is {9, 1}

Since both traversals are the same therefore the output is 1.

Brute Force Approach

The brute force approach to solve this problem is simple and quite intuitive. In this approach, we will store all the leafs of both trees in vectors. Then we will compare whether the leafs are the same or not. 

Algorithm

  1. To solve this problem, we will create a function called is_Leaf_Same() it will take two different arguments, one the root of the first tree and the other being the root of the second tree.
  2. We will make another function get_Leaf_Traversal() which will store the leaf traversal of the tree by using inorder traversal. This function will take only one argument: the tree's root.
  3. After storing the leaf traversals of both the trees in two different vectors, we will compare the values of both the leaf traversals.
  4. We will check if the length of both the vectors is the same; if they are not the same, then we will return 0 from the function, and if they are the same, then we will run a for loop.
  5. In the loop, we will check whether the values are the same. If values are not the same at any point, then we will return 0. Else, we will continue.
  6. After the iteration is over then, we will return 1.

Code in C++

// C++ code to Check if the leaf traversal of two Binary Trees is same
#include <bits/stdc++.h>
using namespace std;

struct Tree
{
    int data;
    Tree *left;
    Tree *right;
    Tree(int x) : data(x), left(NULL), right(NULL) {}
};

// performing  inorder traversal on the tree
void get_Leaf_Traversal(Tree *root, vector<int> &ans)
{
    // leaf node, push it in the vector
    if (!root->left && !root->right)
    {
        ans.push_back(root->data);
        return;
    }

    // call for left subtree
    get_Leaf_Traversal(root->left, ans);

    // call for right subtree
    get_Leaf_Traversal(root->right, ans);
   
    return;
}

bool is_Leaf_Same(Tree *root1, Tree *root2)
{
    vector<int> v1, v2;

    // store the leaf traversal of the first tree
    get_Leaf_Traversal(root1, v1);

    // store the leaf traversal of the second tree
    get_Leaf_Traversal(root2, v2);

    // either of the tree consist of more leafs than the other one then leaf traversal cannot be same
    if (v1.size() != v2.size())
    {
        return 0;
    }

    for (int i = 0; i < v1.size(); i++)
    {
        // if leaf's values are not equal then also leaf traversal cannot be same
        if (v1[i] != v2[i])
            return 0;
    }

    // else the leaf traversal is same
    return 1;
}
int main()
{
    Tree *root1 = new Tree(2);
    root1->left = new Tree(7);
    root1->right = new Tree(5);
    root1->right->left = new Tree(9);
    root1->right->right = new Tree(12);

    Tree *root2 = new Tree(3);
    root2->left = new Tree(2);
    root2->right = new Tree(12);
    root2->left->left = new Tree(7);
    root2->left->right = new Tree(9);

    if (is_Leaf_Same(root1, root2))
    {
        cout << "Yes, leaf traversal for both the trees is the same" << endl;
    }
    else
    {
        cout << "No, leaf traversal for both the trees is not the same" << endl;
    }
}


Output:

Yes, leaf traversal for both the trees is the same.

 

Complexity Analysis 

Time Complexity: Since we are performing the inorder traversal to compute the leafs for both the trees, the time complexity would be O(N), where N would be the number of nodes present in the tree.

Space Complexity: Since we are using extra space in the form of vectors, the vectors are storing all the leaf nodes. Therefore the space complexity is O(N).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In the optimal approach, we will optimize the space complexity. This solution runs simultaneously, but the space complexity would be O(h1+h2), where h1 is the height of the first tree and h2 is the height of the second tree. 

Algorithm

1. To solve this problem, we will create a boolean function called is_Leaf_Same(). It will take two different arguments, one the root of the first tree and the other the root of the second tree.

2. Then we will initialize two stacks, and we will insert the root nodes in the stacks.

3. After, we will run a while loop till both the stacks are not empty. If any stack becomes empty and the other one is not, we will return false. This indicates that one tree has more leaf nodes than the other one.

4. If this is not the case, then we will call the function find_Leaf(), this function will take two arguments one would be the stack, and another would be the current node of the tree.

Tree *head1 = s1.top();
  s1.pop();
  find_Leaf(s1, head1);

  Tree *head2 = s2.top();
  s2.pop();
  find_Leaf(s2, head2);

 

5. In this function, we will run a while loop till we encounter a leaf node or till the root is not NULL. It will look like this:

while (root != NULL && (root->left || root->right))
    {
        // if right node is present then push it in the stack
        if (root->right)
            s.push(root->right);

        // if left node is present then push it in the stack
        if (root->left)
            s.push(root->left);

        root = s.top();
        s.pop();
    }

 

6. After this loop is executed we will return from the function, and the outer loop will continue till the below conditions are not satisfied:

if (!head1 && head2)
          return false;
if (head1 && !head2)
          return false;
if (head1 && head2)
{
   // if the leaf values are not same then return false
     if (head1->data != head2->data)
            return false;

               continue;
  
}

    

7. Here head1 and head2 are the returned leaf noded obtained from the above function call.

8. In the end, we will return true if all the conditions are satisfied.

Code in C++

// C++ code to Check if the leaf traversal of two Binary Trees is same
#include <bits/stdc++.h>
using namespace std;

struct Tree
{
    int data;
    Tree *left;
    Tree *right;
    Tree(int x) : data(x), left(NULL), right(NULL) {}
};

// function to find the leaves
void find_Leaf(stack<Tree *> &s, Tree *&root)
{
    while (root != NULL && (root->left || root->right))
    {
        // if right node is present then push it in the stack
        if (root->right)
            s.push(root->right);

        // if left node is present then push it in the stack
        if (root->left)
            s.push(root->left);

        root = s.top();
        s.pop();
    }
}

bool is_Leaf_Same(Tree *root1, Tree *root2)
{
    stack<Tree *> s1, s2;

    // push root1 to empty stack q1
    s1.push(root1);

    // push root2 to empty stack q2
    s2.push(root2);

    // loop until either of stack are non-empty.
    while (!s1.empty() || !s2.empty())
    {
        // if any of the trees has extra leaves then return false
        if (s1.empty() || s2.empty())
            return false;

        Tree *head1 = s1.top();
        s1.pop();
        find_Leaf(s1, head1);
        Tree *head2 = s2.top();
        s2.pop();
        find_Leaf(s2, head2);

        if (!head1 && head2)
            return false;
        if (head1 && !head2)
            return false;
        if (head1 && head2)
        {
            // if the leaf values are not same then return false
            if (head1->data != head2->data)
                return false;

            continue;
        }
    }

    // else the leaf traversal is same
    return 1;
}
int main()
{
    Tree *root1 = new Tree(4);
    root1->left = new Tree(7);
    root1->right = new Tree(5);
    root1->right->left = new Tree(9);
    root1->right->right = new Tree(12);

    Tree *root2 = new Tree(3);
    root2->left = new Tree(2);
    root2->right = new Tree(12);
    root2->left->left = new Tree(7);
    root2->left->right = new Tree(9);

    if (is_Leaf_Same(root1, root2))
    {
        cout << "Yes, leaf traversal for both the trees is the same" << endl;
    }
    else
    {
        cout << "No, leaf traversal for both the trees is not the same" << endl;
    }
}

 

Output:

Yes, leaf traversal for both the trees is the same

 

Complexity Analysis

Time Complexity: Since we are traversing both the trees simultaneously, time complexity would be O(N).

Space Complexity: Since we are using extra space to store the nodes in the stack, the space complexity would be O(h1+h2). Here, h1 is the height of the first tree and h2 is the height of the second tree.

Frequently asked questions

How do you know if a binary tree is complete?

A complete binary tree means that all the nodes in that tree have either zero or two children. We can check it by traversing through the whole tree and checking each node for the condition on the number of child nodes it can have.

What is preorder traversal in a binary tree?

In the preorder traversal of a tree, we always process the root first, then we process the left subtree of the root, and in the end, we process the right subtree of the root. 

The order looks like this:

root --> left --> right

What is a skewed binary tree?

A skewed binary tree is a binary tree where every node has either one child or does not have any child.

There are two types of skewed trees:

1. Left Skewed Binary Tree

2. Right Skewed Binary Tree

Conclusion

In this article, we have discussed the problem of checking whether the leaf traversal of two binary trees is same. We have discussed two approaches for this problem: the brute force approach and the optimized approach. We have also discussed the time complexities and space complexities of both approaches.

We hope you have gained a better understanding of the solution to this problem, and now it is your responsibility to solve it and try some new and different approaches. 

If you want to practice problems on binary trees, you can refer to these links:

  1. LCA of three Nodes
  2. Longest Univalue Path
  3. Boundary Traversal of Binary Tree
  4. Time To Burn Tree
     

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingDatabase Management Systems, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding.

Previous article
Count Nodes having the Highest Value in the Path from the Root to itself in a Binary Tree
Next article
Check if a binary tree contains node values are in strictly increasing and decreasing order at even and odd levels
Live masterclass