Given two binary trees, check whether the leaf traversals of both trees are the same or not.
For example, the leaf traversals of the following binary trees are 4, 5, 6.
A simple solution is to traverse the first tree using inorder traversal and store each encountered leaf in an array. Repeat the same for the second BST. Then the problem reduces to comparing two arrays for equality. The time complexity of this approach is O(m + n), and the additional space used is O(m + n). Here m is the total number of nodes in the first tree, and n is the total number of nodes in the second tree.
The idea is to traverse both trees simultaneously using the iterative preorder traversal and compare data of each encountered leaf node, i.e., the i'th leaf in the first tree is compared with the i'th leaf in the second tree. The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include <iostream>
#include <stack>
using namespace std;
// A BST Node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
// Utility function to check if a given node is a leaf node
bool isLeaf(Node* node) {
return node->left == nullptr && node->right == nullptr;
}
// Utility function to return the next leaf node in a pre-order sequence
Node* getNextLeafNode(stack<Node*> &s) {
// continue the pre-order sequence from the top node of the stack
Node* curr = s.top();
s.pop();
// repeat until leaf node is encountered
while (!isLeaf(curr))
{
// push the right child of the popped node to the stack before the
// left child (Since the stack follows LIFO semantics, the left child
// is processed before the right child)
if (curr->right != nullptr) { s.push(curr->right); }
if (curr->left != nullptr) { s.push(curr->left); }
// update the current node to the top node of the stack
curr = s.top();
s.pop();
}
// current node will be a leaf at this point
return curr;
}
// Function to check if the leaf traversal of two given binary trees is the same
bool isLeafTraversalSame(Node* x, Node* y) {
// create two empty stacks
stack<Node*> first;
stack<Node*> second;
// push the root node of the first and second tree to the first and
// second stack, respectively
first.push(x);
second.push(y);
// loop till either of the stack is empty
while (!first.empty() && !second.empty())
{
// get the next leaf in a pre-order sequence of the first tree
Node* xLeaf = getNextLeafNode(first);
// get the next leaf in a pre-order sequence of the second tree
Node* yLeaf = getNextLeafNode(second);
// return false if their data doesn’t match
if (xLeaf->data != yLeaf->data) {
return false;
}
}
// return true only if both stacks are empty at this point;
// if any of the stacks is not empty, that means some tree
// contains more leaf nodes
return first.empty() && second.empty();
}
int main()
{
Node* x = new Node(1);
x->left = new Node(2);
x->right = new Node(3);
x->left->left = new Node(4);
x->left->right = new Node(5);
x->right->left = new Node(6);
Node* y = new Node(1);
y->left = new Node(2);
y->right = new Node(3);
y->left->right = new Node(4);
y->right->left = new Node(5);
y->right->right = new Node(6);
bool isSame = isLeafTraversalSame(x, y);
if (isSame) {
cout << “The tree traversals are the same” << endl;
}
else {
cout << “The tree traversals are different” << endl;
}
return 0;
}
|
Output:
The tree traversals are the same
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
import java.util.Stack;
// A BST Node
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
class Main
{
// Utility function to check if a given node is a leaf node
private static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}
// Utility function to return the next leaf node in a pre-order sequence
private static Node getNextLeafNode(Stack<Node> s) {
// continue the pre-order sequence from the top node of the stack
Node curr = s.pop();
// repeat until leaf node is encountered
while (!isLeaf(curr)) {
// push the right child of the popped node to the stack before the
// left child (Since the stack follows LIFO semantics, the left child
// is processed before the right child)
if (curr.right != null) { s.push(curr.right); }
if (curr.left != null) { s.push(curr.left); }
// update the current node to the top node of the stack
curr = s.pop();
}
// current node will be a leaf at this point
return curr;
}
// Function to check if the leaf traversal of two given binary trees is the same
public static boolean isLeafTraversalSame(Node x, Node y) {
// create two empty stacks
Stack<Node> first = new Stack<>();
Stack<Node> second = new Stack<>();
// push the root node of the first and second tree to the first and
// second stack, respectively
first.push(x);
second.push(y);
// loop till either of the stack is empty
while (!first.empty() && !second.empty())
{
// get the next leaf in a pre-order sequence of the first tree
Node xLeaf = getNextLeafNode(first);
// get the next leaf in a pre-order sequence of the second tree
Node yLeaf = getNextLeafNode(second);
// return false if their data doesn’t match
if (xLeaf.data != yLeaf.data) {
return false;
}
}
// return true only if both stacks are empty at this point;
// if any of the stacks is not empty, that means some tree
// contains more leaf nodes
return first.empty() && second.empty();
}
public static void main(String[] args)
{
Node x = new Node(1);
x.left = new Node(2);
x.right = new Node(3);
x.left.left = new Node(4);
x.left.right = new Node(5);
x.right.left = new Node(6);
Node y = new Node(1);
y.left = new Node(2);
y.right = new Node(3);
y.left.right = new Node(4);
y.right.left = new Node(5);
y.right.right = new Node(6);
boolean isSame = isLeafTraversalSame(x, y);
if (isSame) {
System.out.println(“The tree traversals are the same”);
}
else {
System.out.println(“The tree traversals are different”);
}
}
}
|
Output:
The tree traversals are the same
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
from collections import deque
# A BST Node
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Utility function to check if a given node is a leaf node
def isLeaf(node):
return node.left is None and node.right is None
# Utility function to return the next leaf node in a pre-order sequence
def getNextLeafNode(s):
# continue the pre-order sequence from the top node of the stack
curr = s.pop()
# repeat until a leaf node is encountered
while not isLeaf(curr):
# push the right child of the popped node to the stack before the
# left child (Since the stack follows LIFO semantics, the left child
# is processed before the right child)
if curr.right:
s.append(curr.right)
if curr.left:
s.append(curr.left)
# update the current node to the top node of the stack
curr = s.pop()
# current node will be a leaf at this point
return curr
# Function to check if the leaf traversal of two given binary trees is the same
def isLeafTraversalSame(x, y):
# create two empty stacks
first = deque()
second = deque()
# push the root node of the first and second tree to the first and
# second stack, respectively
first.append(x)
second.append(y)
# loop till either of the stack is empty
while first and second:
# get the next leaf in a pre-order sequence of the first tree
xLeaf = getNextLeafNode(first)
# get the next leaf in a pre-order sequence of the second tree
yLeaf = getNextLeafNode(second)
# return false if their data doesn’t match
if xLeaf.data != yLeaf.data:
return False
# return true only if both stacks are empty at this point;
# if any of the stacks is not empty, that means the tree
# contains more leaf nodes
return not first and not second
if __name__ == ‘__main__’:
x = Node(1)
x.left = Node(2)
x.right = Node(3)
x.left.left = Node(4)
x.left.right = Node(5)
x.right.left = Node(6)
y = Node(1)
y.left = Node(2)
y.right = Node(3)
y.left.right = Node(4)
y.right.left = Node(5)
y.right.right = Node(6)
isSame = isLeafTraversalSame(x, y)
if isSame:
print(“The tree traversals are the same”)
else:
print(“The tree traversals are different”)
|
Output:
The tree traversals are the same
Download Run Code
Output:
The tree traversals are the same
Download Run Code
Output:
The tree traversals are the same
Download Run Code
Output:
The tree traversals are the same
The time complexity of the above solution is O(m + n), where m is the total number of nodes in the first tree and n is the total number of nodes in the second tree. Extra space of O(x + y) is used for the stack data structure where x is the height of the first tree, and y is the height of the second tree.
Another approach is to connect leaf nodes in the form of a linked list and then traverse both lists and compare their data. Following is the C++, Java, and Python program that demonstrates it:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
#include <iostream>
using namespace std;
// Binary tree node
struct Node
{
int key;
Node *left, *right;
Node(int key)
{
this->key = key;
this->left = this->right = nullptr;
}
};
// Utility function to check if a given node is a leaf node
bool isLeaf(Node *node) {
return node->left == nullptr && node->right == nullptr;
}
// Recursive function to connect leaf nodes of a given tree
void connectLeafNodes(Node* root, Node* &head, Node* &prev)
{
// base case
if (root == nullptr) {
return;
}
// If the current node is a leaf node, connect it with the previous leaf node
// using the right pointer. If the previous leaf node does not exist,
// make the current node as head of the list
if (isLeaf(root))
{
if (prev == nullptr) {
head = root;
} else {
prev->right = root;
}
prev = root;
}
// recur for the left and the right subtree
connectLeafNodes(root->left, head, prev);
connectLeafNodes(root->right, head, prev);
}
// Function to check if the leaf traversal of two given binary trees is the same
bool isLeafTraversalSame(Node* x, Node* y)
{
// connect leaf nodes of the first binary tree into a linked list
Node* first = nullptr;
Node* prev = nullptr;
connectLeafNodes(x, first, prev);
// connect leaf nodes of the second binary tree into a linked list
Node* second = nullptr;
prev = nullptr;
connectLeafNodes(y, second, prev);
// compare both lists and break the loop on the first data mismatch
while (first && second && first->key == second->key)
{
first = first->right;
second = second->right;
}
// return true only if both lists are empty at this point;
// if any of the lists are not empty, that means the tree
// contains more leaf nodes or leaf nodes doesn’t match
return !first && !second;
}
int main()
{
Node* x = new Node(1);
x->left = new Node(2);
x->right = new Node(3);
x->left->left = new Node(4);
x->left->right = new Node(5);
x->right->left = new Node(6);
Node* y = new Node(1);
y->left = new Node(2);
y->right = new Node(3);
y->left->right = new Node(4);
y->right->left = new Node(5);
y->right->right = new Node(6);
bool isSame = isLeafTraversalSame(x, y);
if (isSame) {
cout << “The tree traversals are the same”;
}
else {
cout << “The tree traversals are different”;
}
return 0;
}
|
Output:
The tree traversals are the same
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
// Binary tree node
class Node
{
int key;
Node left, right;
Node(int key) {
this.key = key;
this.left = this.right = null;
}
}
class Main {
// Wrapper over Node class
static class NodeWrapper {
public Node node;
}
// Utility function to check if a given node is a leaf node
public static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}
// Recursive function to connect leaf nodes of a given tree
public static void connectLeafNodes(Node root, NodeWrapper head, NodeWrapper prev)
{
// base case
if (root == null) {
return;
}
// If the current node is a leaf node, connect it with the previous leaf node
// using the right pointer. If the previous leaf node does not exist,
// make the current node as head of the list
if (isLeaf(root))
{
if (prev.node == null) {
head.node = root;
} else {
prev.node.right = root;
}
prev.node = root;
}
// recur for the left and the right subtree
connectLeafNodes(root.left, head, prev);
connectLeafNodes(root.right, head, prev);
}
// Function to check if the leaf traversal of two given binary trees is the same
public static boolean isLeafTraversalSame(Node x, Node y)
{
// connect leaf nodes of the first binary tree into a linked list
NodeWrapper first = new NodeWrapper();
NodeWrapper prev = new NodeWrapper();
connectLeafNodes(x, first, prev);
// connect leaf nodes of the second binary tree into a linked list
NodeWrapper second = new NodeWrapper();
prev.node = null;
connectLeafNodes(y, second, prev);
x = first.node;
y = second.node;
// compare both lists and break the loop on `x` data mismatch
while (x != null && y != null && x.key == y.key) {
x = x.right;
y = y.right;
}
// return true only if both lists are empty at this point;
// if any of the lists are not empty, that means the tree
// contains more leaf nodes or leaf nodes doesn’t match
return x == null && y == null;
}
public static void main(String[] args)
{
Node x = new Node(1);
x.left = new Node(2);
x.right = new Node(3);
x.left.left = new Node(4);
x.left.right = new Node(5);
x.right.left = new Node(6);
Node y = new Node(1);
y.left = new Node(2);
y.right = new Node(3);
y.left.right = new Node(4);
y.right.left = new Node(5);
y.right.right = new Node(6);
boolean isSame = isLeafTraversalSame(x, y);
if (isSame) {
System.out.println(“The tree traversals are the same”);
}
else {
System.out.println(“The tree traversals are different”);
}
}
}
|
Output:
The tree traversals are the same
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
# Binary Tree Node
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
# Utility function to check if a given node is a leaf node
def isLeaf(node):
return node.left is None and node.right is None
# Recursive function to connect leaf nodes of a given tree
def connectLeafNodes(root, head=None, prev=None):
# base case
if root is None:
return head, prev
# If the current node is a leaf node, connect it with the previous leaf node
# using the right pointer. If the previous leaf node does not exist,
# make the current node as head of the list
if isLeaf(root):
if prev is None:
head = root
else:
prev.right = root
prev = root
# recur for the left and the right subtree
(head, prev) = connectLeafNodes(root.left, head, prev)
return connectLeafNodes(root.right, head, prev)
# Function to check if the leaf traversal of two given binary trees is the same
def isLeafTraversalSame(x, y):
# connect leaf nodes of the first binary tree into a linked list
first, prev = connectLeafNodes(x)
# connect leaf nodes of the second binary tree into a linked list
second, prev = connectLeafNodes(y)
# compare both lists and break the loop on the first data mismatch
while first and second and first.key == second.key:
first = first.right
second = second.right
# return true only if both lists are empty at this point;
# if any of the lists are not empty, that means the tree
# contains more leaf nodes, or leaf nodes doesn’t match
return first is None and second is None
if __name__ == ‘__main__’:
x = Node(1)
x.left = Node(2)
x.right = Node(3)
x.left.left = Node(4)
x.left.right = Node(5)
x.right.left = Node(6)
y = Node(1)
y.left = Node(2)
y.right = Node(3)
y.left.right = Node(4)
y.right.left = Node(5)
y.right.right = Node(6)
isSame = isLeafTraversalSame(x, y)
if isSame:
print(“The tree traversals are the same”)
else:
print(“The tree traversals are different”)
|
Output:
The tree traversals are the same
The tree traversals are the same
Download Run Code
Output:
The tree traversals are the same