## 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

- 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.
- 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.
- After storing the leaf traversals of both the trees in two different vectors, we will compare the values of both the leaf traversals.
- 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.
- 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.
- 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).