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

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);

You can also try this code with Online C++ Compiler

Run Code

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();
    }

You can also try this code with Online C++ Compiler

Run Code

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;
  
}

You can also try this code with Online C++ Compiler

Run Code

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;
    }
}

You can also try this code with Online C++ Compiler

Run Code

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 Algorithms, Competitive Programming, Database 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 problems, interview 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.