Check whether the leaf traversal of given binary trees is the same or not
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 tree. 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.
1. Using Iterative Preorder Traversal
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 108 109 110 111 112 113 114 115 116 |
#include <iostream> #include <stack> using namespace std; // Data structure to store a binary tree 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 preorder sequence Node* getNextLeafNode(stack<Node*> &s) { // continue the preorder sequence from the top node of the stack Node* curr = s.top(); s.pop(); // repeat till a leaf node is encountered while (curr != nullptr && !isLeaf(curr)) { // push the right child of the popped node into 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 into the first and // second stack, respectively first.push(x); second.push(y); // loop till a stack becomes empty while (!first.empty() && !second.empty()) { // get the next leaf in a preorder sequence of the first tree Node* xLeaf = getNextLeafNode(first); // get the next leaf in a preorder sequence of the second tree Node* yLeaf = getNextLeafNode(second); if (xLeaf == nullptr && yLeaf == nullptr) { return true; } // return false if their data doesn't match if (xLeaf == nullptr || yLeaf == nullptr || 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 103 104 105 106 107 108 109 110 111 112 113 |
import java.util.Stack; // A class to store a binary tree 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 preorder sequence private static Node getNextLeafNode(Stack<Node> s) { // continue the preorder sequence from the top node of the stack Node curr = s.pop(); // repeat till a leaf node is encountered while (curr != null && !isLeaf(curr)) { // push the right child of the popped node into 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 into the first and // second stack, respectively first.push(x); second.push(y); // loop till a stack becomes empty while (!first.empty() && !second.empty()) { // get the next leaf in a preorder sequence of the first tree Node xLeaf = getNextLeafNode(first); // get the next leaf in a preorder sequence of the second tree Node yLeaf = getNextLeafNode(second); if (xLeaf == null && yLeaf == null) { return true; } // return false if their data doesn't match if (xLeaf == null || yLeaf == null || 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 96 97 |
from collections import deque # A class to store a binary tree 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 preorder sequence def getNextLeafNode(s): # continue the preorder sequence from the top node of the stack curr = s.pop() # repeat till a leaf node is encountered while curr and not isLeaf(curr): # push the right child of the popped node into 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 into the first and # second stack, respectively first.append(x) second.append(y) # loop till a stack becomes empty while first and second: # get the next leaf in a preorder sequence of the first tree xLeaf = getNextLeafNode(first) # get the next leaf in a preorder sequence of the second tree yLeaf = getNextLeafNode(second) if xLeaf is None and yLeaf is None: return True # return false if their data doesn't match if xLeaf is None or yLeaf is None or 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
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. The 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.
2. Connect Leaf Nodes
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 100 |
#include <iostream> using namespace std; // Data structure to store a 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 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 the leaf nodes don'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 104 105 106 |
// Data structure to store a 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 child. 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 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 the leaf nodes don'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 |
# Data structure to store a 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 child. 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 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 the leaf nodes don'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
Also See:
Iteratively print the leaf to root path for every leaf node in a binary tree
Set next pointer to the inorder successor of all nodes in a binary tree
Print all paths from the root to leaf nodes of a binary tree
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)