Check if leaf traversal of two Binary Trees is same | GeeksforGeeks


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!

Leave a Reply

Your email address will not be published. Required fields are marked *