Hello friends!

And, welcome to another tutorial on GeeksforGeeks. In this video we are going to understand the

program which helps us in checking if leaf traversal of two binary trees is same.

First, let us take an example. In the first example, we have leaf traversal

as 8 9 2 and 8 2 9. So, its not same. In the second example, the leaf traversal

of both the trees are 4 6 7. Now let us look at the algorithm which will assist us

in finding if leaf traversal of two binary trees is same. Let us also have sample trees to test our

algorithm. We will use two stacks. We will push the root nodes of both both trees

into stack 1 and stack 2 respectively. So, the root node of tree 1

which is 1 is pushed into stack 1. In the next step, we push the root node of

tree 2 into stack 2. So, 0 will be pushed into stack 2 Now, we loop until either of two stacks is

not empty. We enter the outer while loop and check if one of the two stacks is empty.

Since it is not, we have another variable temp1 to store the top variable to

stack 1 and pop it. Now, we check if the popped node is not null

and it is not a leaf node as well. Since temp1=1 and 1 has both left and right

child, it is not a leaf node. So, both conditions are satisfied and we enter the

first inner while loop.In the next step, we push the right and left children of temp1.

So, first the right child of 1 which is 3 is

pushed into stack 1. Next, we push the left child of temp1 which

is 2 into stack 1. Again, we pop the top element from stack 1

and assign it to temp. So, temp will now point to 2. We check if temp is not null and if temp is

not a leaf node. Since both conditions are satisfied, we loop again. Now, again we

push the left and right child of temp1.Since the right child of 2 does not

exist, nothing is pushed.The left child of temp1 is 4, So, 4 is pushed into stack 1. Now, we pop element from stack 1. So, 4 will

be popped and temp1 will be pointing to 4. Since 4 is a leaf node, the second condition

in the while loop is not satisfied so we come out of the first inner while loop. Now,

we do the same for tree 2. So we pop the top element from stack 2 and assign it

to temp2. So, temp2 will point to 0. We enter the second inner while loop since

temp2 is not null and 0 is not a leaf node. So, we push the right and left child

of 0 which are 8 and 5 into stack 2. Now, we pop the top element from stack 2 and

assign it to temp2. So, temp2 will point to 5. Again, we check if temp2 is not null and if

temp2 is not a leaf node. Since, both conditions are satisfied, we enter the second

inner while loop again. Now, we push the right and left child of 5. The right

child of 5 which is 4 is pushed into stack 2. Since, the left child of 5 is null, nothing

is enqueued into stack 2. So, again we pop the top element from stack 2 and assign it

to temp2. Hence, temp2 will now point to 4. Since 4 is a leaf node, the second condition

in the while loop is not satisfied and we come out of the second inner while loop.

Now, we check if one out of temp1 and temp2 is null and other is not. Since

both are not null, we compare the data of temp1 and temp2 since both are equal, we continue

execution for the outer for loop. Again, we pop the element from stack

1 and hence 3 will be popped and temp1 will now point to 3. Now, we push the left and right child of temp1.So,

we push 7, which is the right child of 3 first into stack 1. Now, we push the left child of 3 which is

6 into stack 1. We pop the top element from stack 1 and assign

it to temp1. SO, temp1 will now point to 6. We check if temp1 is not null and if temp1

is not a leaf node. SInce, 6 does not have both left and right child, it is a leaf

node and hence we come out of the first inner while loop. We repeat the same for stack

2. So, we pop the top element from stack 2 and assign it to temp2. Now,

temp2 will point to 8. WE check if 8 is not null and if 8 is not

leaf node. Since both conditions are satisfied, we enter the second inner while

loop. We push the left and right child of node 8. So, we pugh 7 and 6 into stack 2. Again, we will pop 6 from stack 2. So, temp2

will point to 6. Now, we will check if temp2 is not null or

if temp2 is not a leaf node. Since, 6 does not have both left and right child, it is

a leaf node and hence we come out of the second inner while loop. We check if one of

temp1 and temp2 is null and other is not.Since both are not null, we compare the

data of temp1 and temp2. SInce both are equal,we continue with the outer while

loop. Again, since neither of the two stack is empty, we pop the element from stack

1. So, temp1 will now point to 7 and 7 will be popped. We check if temp1 is not null and if temp1

is not a leaf node. SInce, 7 does not have any child, it is a leaf node and we skip

the first inner while loop. We repeat the same for the second tree. Temp2 will point

to 7 and 7 will be popped. AGain, we check if temp2 is not null and that

if temp2 is not a leaf node. Since 7 is a leaf node in tree 2 as well, we skip the

second inner while loop Now, we check if either of temp1 and temp2 is null. Since both

are not, we move on and compare data of the two. As both data are equal, we

move on to the outer while loop. Now, wince stack 1 and stack 2 both are empty,

we come out of the outer while loop and finally return true. So, the leaf order

traversal for both trees is same. Now, let us have a look at the time complexity of the

program. This code will run in O(n) complexity.Heren

are the number of nodes in our tree. With this we come to an end of this tutorial. For any doubts or suggestions please leave

them in the comment section below. Thanks for watching!