Posted on by Kalkicode
Code Stack

# Check if leaf traversal of two Binary Trees is same or not

The problem "Check if leaf traversal of two Binary Trees is same or not" involves checking whether the leaf nodes' traversal of two given binary trees is the same or not. A leaf node is a node in the tree that does not have any children (i.e., both left and right children are null). The leaf nodes' traversal refers to the sequence of leaf node values encountered while traversing the tree from left to right.

## Problem Statement

Given two binary trees, we need to check whether their leaf nodes' traversal is the same or not.

## Example

Consider the following two binary trees:

``````First Binary Tree (x):

6
/ \
7   11
/ \  / \
8  1  5  6

Second Binary Tree (y):

36
/ \
2   17
\  / \
1 5  6
/ \
8   1

Third Binary Tree (z):

36
/ \
2   17
\  / \
1 5  6
/ \
1   8
``````

The leaf traversal for the first tree (x) is `[8, 1, 5, 6]`, for the second tree (y) is `[8, 1, 5, 6]`, and for the third tree (z) is `[1, 8, 5, 6]`.

## Idea to Solve the Problem

To check if the leaf traversal of two binary trees is the same or not, we can use a stack data structure to collect the leaf nodes' data while performing an inorder traversal of each tree. Then, we compare the leaf nodes' data collected for both trees to determine if they are identical.

## Algorithm

1. Create a stack `s1` and a stack `s2` to collect leaf node data for the first and second binary trees, respectively.
2. Perform an inorder traversal of the first binary tree and collect its leaf nodes' data into `s1` using the `getLeafNodes` function.
3. Perform an inorder traversal of the second binary tree and collect its leaf nodes' data into `s2` using the same `getLeafNodes` function.
4. Compare the contents of `s1` and `s2` to check if the leaf traversal is the same or not.
5. Return `true` if the leaf traversal is the same and `false` otherwise.

## Pseudocode

``````Function isLeafSame(tree1, tree2):
Create an empty stack s1
Create an empty stack s2

Perform inorder traversal of tree1 using getLeafNodes(tree1, s1)
Perform inorder traversal of tree2 using getLeafNodes(tree2, s2)

Initialize a variable result to true

While s1 is not empty and s2 is not empty:
If s1.peek() is not equal to s2.peek():
Set result to false
Pop an element from s1
Pop an element from s2

Return result and check if s1 is empty and s2 is empty

Function getLeafNodes(node, stack):
If node is null:
Return
If node.left is null and node.right is null:
Push node.data onto stack
Return
Recursively call getLeafNodes(node.left, stack)
Recursively call getLeafNodes(node.right, stack)
``````

## Time Complexity

The time complexity of the algorithm is O(n) since we traverse each node of both binary trees once, where n is the total number of nodes in both trees. The operations of pushing and popping elements into and from the stack take constant time. Therefore, the overall time complexity is linear.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post