Check if leaf traversal of two Binary Trees is same? - GeeksforGeeks
Leaf traversal is sequence of leaves traversed from left to right. The problem is to check if leaf traversals of two given Binary Trees are same or not.
Expected time complexity O(n). Expected auxiliary space O(h1 + h2) where h1 and h2 are heights of two Binary Trees.
Read full article from Check if leaf traversal of two Binary Trees is same? - GeeksforGeeks
Leaf traversal is sequence of leaves traversed from left to right. The problem is to check if leaf traversals of two given Binary Trees are same or not.
Expected time complexity O(n). Expected auxiliary space O(h1 + h2) where h1 and h2 are heights of two Binary Trees.
Input: Roots of below Binary Trees 1 / \ 2 3 / / \ 4 6 7 0 / \ 5 8 \ / \ 4 6 7 Output: same Leaf order traversal of both trees is 4 6 7
A Simple Solution is traverse first tree and store leaves from left and right in an array. Then traverse other tree and store leaves in another array. Finally compare two arrays. If both arrays are same, then return true.
The above solution requires O(m+n) extra space where m and n are nodes in first and second tree respectively.
How to check with O(h1 + h2) space?
The idea is use iterative traversal. Traverse both trees simultaneously, look for a leaf node in both trees and compare the found leaves. All leaves must match.
The idea is use iterative traversal. Traverse both trees simultaneously, look for a leaf node in both trees and compare the found leaves. All leaves must match.
// Returns true of leaf traversal of two trees is
// same, else false
public
static
boolean
isSame(Node root1, Node root2)
{
// Create empty stacks. These stacks are going
// to be used for iterative traversals.
Stack<Node> s1 =
new
Stack<Node>();
Stack<Node> s2 =
new
Stack<Node>();
s1.push(root1);
s2.push(root2);
// Loop until either of two stacks is not empty
while
(!s1.empty() || !s2.empty())
{
// If one of the stacks is empty means other
// stack has extra leaves so return false
if
(s1.empty() || s2.empty())
return
false
;
Node temp1 = s1.pop();
while
(temp1!=
null
&& !temp1.isLeaf())
{
// Push right and left children of temp1.
// Note that right child is inserted
// before left
if
(temp1.right !=
null
)
s1.push(temp1. right);
if
(temp1.left !=
null
)
s1.push(temp1.left);
temp1 = s1.pop();
}
// same for tree2
Node temp2 = s2.pop();
while
(temp2!=
null
&& !temp2.isLeaf())
{
if
(temp2.right !=
null
)
s2.push(temp2.right);
if
(temp2.left !=
null
)
s2.push(temp2.left);
temp2 = s2.pop();
}
// If one is null and other is not, then
// return false
if
(temp1==
null
&& temp2!=
null
)
return
false
;
if
(temp1!=
null
&& temp2==
null
)
return
false
;
// If both are not null and data is not
// same return false
if
(temp1!=
null
&& temp2!=
null
)
{
if
(temp1.data != temp2.data)
return
false
;
}
}
// If control reaches this point, all leaves
// are matched
return
true
;
}