Find first non matching leaves in two binary trees
Given two binary trees, find the first leaves of two trees that do not match. If there are no non-matching leaves, print nothing.
Examples:
Input : First Tree 5 / \ 2 7 / \ 10 11 Second Tree 6 / \ 10 15 Output : 11 15 If we consider leaves of two trees in order, we can see that 11 and 15 are the first leaves that do not match.
Method 1 (Simple) :
Do Inorder traversal of both trees one by one, store the leaves of both trees in two different lists. Finally, find first values which are different in both lists. Time complexity is O(n1 + n2) where n1 and n2 are number of nodes in two trees. Auxiliary space requirement is O(n1 + n2).
C++
// C++ program to find first leaves that are // not same. #include<bits/stdc++.h> using namespace std; // Tree node struct Node{ int data; Node *left, *right; }; // Utility method to create a new node Node *newNode( int x){ Node * temp = new Node; temp->data = x; temp->left = temp->right = NULL; return temp; } // function to store leaf nodes in // inorder fashion void inorder(Node* root, vector< int > &list){ if (root == NULL) return ; inorder(root->left, list); if (root->left == NULL && root->right == NULL){ list.push_back(root->data); } inorder(root->right, list); } // Prints the first non-matching leaf node in // two trees if it exists, else prints nothing. void findFirstUnmatch(Node *root1, Node *root2){ vector< int > list1, list2; inorder(root1, list1); inorder(root2, list2); int n = min(list1.size(), list2.size()); for ( int i = 0; i<n; i++){ if (list1[i] != list2[i]){ cout<< "First non matching leaves: " <<list1[i]<< " " <<list2[i]<<endl; return ; } } } // Driver code int main(){ struct Node *root1 = newNode(5); root1->left = newNode(2); root1->right = newNode(7); root1->left->left = newNode(10); root1->left->right = newNode(11); struct Node * root2 = newNode(6); root2->left = newNode(10); root2->right = newNode(15); findFirstUnmatch(root1,root2); return 0; } // this code is contributed by Yash Agarwal(yashagarwal2852002) |
Java
// Java program to find first leaves that are not same. import java.util.*; // Tree node class Node { int data; Node left, right; // constructor Node( int item) { data = item; left = right = null ; } } // Main class public class Main { // Utility method to store leaf nodes in inorder fashion static void inorder(Node root, List<Integer> list) { if (root == null ) return ; inorder(root.left, list); if (root.left == null && root.right == null ) { list.add(root.data); } inorder(root.right, list); } // Prints the first non-matching leaf node in two trees if it exists, else prints nothing. static void findFirstUnmatch(Node root1, Node root2) { List<Integer> list1 = new ArrayList<Integer>(); List<Integer> list2 = new ArrayList<Integer>(); inorder(root1, list1); inorder(root2, list2); int n = Math.min(list1.size(), list2.size()); for ( int i = 0 ; i < n; i++) { if (list1.get(i) != list2.get(i)) { System.out.println( "First non matching leaves: " + list1.get(i) + " " + list2.get(i)); return ; } } } // Driver code public static void main(String[] args) { Node root1 = new Node( 5 ); root1.left = new Node( 2 ); root1.right = new Node( 7 ); root1.left.left = new Node( 10 ); root1.left.right = new Node( 11 ); Node root2 = new Node( 6 ); root2.left = new Node( 10 ); root2.right = new Node( 15 ); findFirstUnmatch(root1, root2); } } |
Python3
# Python program to find first leaves that are # not same. import sys # Tree node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # function to store leaf nodes in # inorder fashion def inorder(root, lst): if not root: return inorder(root.left, lst) if not root.left and not root.right: lst.append(root.data) inorder(root.right, lst) # Prints the first non-matching leaf node in # two trees if it exists, else prints nothing. def findFirstUnmatch(root1, root2): lst1, lst2 = [], [] inorder(root1, lst1) inorder(root2, lst2) n = min ( len (lst1), len (lst2)) for i in range (n): if lst1[i] ! = lst2[i]: print (f "First non-matching leaves: {lst1[i]} {lst2[i]}" ) return # Driver code if __name__ = = '__main__' : root1 = Node( 5 ) root1.left = Node( 2 ) root1.right = Node( 7 ) root1.left.left = Node( 10 ) root1.left.right = Node( 11 ) root2 = Node( 6 ) root2.left = Node( 10 ) root2.right = Node( 15 ) findFirstUnmatch(root1,root2) |
Javascript
// JavaScript program to find first leaves that are // not same // tree node class Node{ constructor(data){ this .data = data; this .left = this .right = null ; } } // utility function to create a new node function newNode(x){ return new Node(x); } // function to store leaf nodes in // inorder fashion function inorder(root, list){ if (root == null ) return ; inorder(root.left, list); if (root.left == null && root.right == null ) list.push(root.data); inorder(root.right, list); } // Prints the first non-matching leaf node in // two trees if it exists, else prints nothing. function findFirstUnmatch(root1, root2){ let list1 = []; let list2 = []; inorder(root1, list1); inorder(root2, list2); let n = Math.min(list1.length, list2.length); for (let i = 0; i<n; i++){ if (list1[i] != list2[i]){ console.log( "First non matching leaves : " + list1[i] + " " + list2[i]); return ; } } } // driver code let root1 = newNode(5); root1.left = newNode(2); root1.right = newNode(7); root1.left.left = newNode(10); root1.left.right = newNode(11); let root2 = newNode(6); root2.left = newNode(10); root2.right = newNode(15); findFirstUnmatch(root1, root2); |
C#
using System; using System.Collections.Generic; // Tree node public class Node { public int data; public Node left, right; public Node( int x) { data = x; left = right = null ; } } public class Program { // Utility method to create a new node static Node NewNode( int x) { Node temp = new Node(x); return temp; } // function to store leaf nodes in // inorder fashion static void Inorder(Node root, List< int > list) { if (root == null ) return ; Inorder(root.left, list); if (root.left == null && root.right == null ) { list.Add(root.data); } Inorder(root.right, list); } // Prints the first non-matching leaf node in // two trees if it exists, else prints nothing. static void FindFirstUnmatch(Node root1, Node root2) { List< int > list1 = new List< int >(); List< int > list2 = new List< int >(); Inorder(root1, list1); Inorder(root2, list2); int n = Math.Min(list1.Count, list2.Count); for ( int i = 0; i < n; i++) { if (list1[i] != list2[i]) { Console.WriteLine( "First non matching leaves: " + list1[i] + " " + list2[i]); return ; } } } // Driver code static void Main() { Node root1 = NewNode(5); root1.left = NewNode(2); root1.right = NewNode(7); root1.left.left = NewNode(10); root1.left.right = NewNode(11); Node root2 = NewNode(6); root2.left = NewNode(10); root2.right = NewNode(15); FindFirstUnmatch(root1, root2); } } |
First non matching leaves: 11 15
Method 2 (Efficient):
This solution auxiliary space requirement as O(h1 + h2) where h1 and h2 are heights of trees. We do Iterative Preorder traversal of both the trees simultaneously using stacks. We maintain a stack for each tree. For every tree, keep pushing nodes in the stack till the top node is a leaf node. Compare the two top nodes f both the stack. If they are equal, do further traversal else return.
Implementation:
C++
// C++ program to find first leaves that are // not same. #include<bits/stdc++.h> using namespace std; // Tree node struct Node { int data; Node *left, *right; }; // Utility method to create a new node Node *newNode( int x) { Node * temp = new Node; temp->data = x; temp->left = temp->right = NULL; return temp; } bool isLeaf(Node * t) { return ((t->left == NULL) && (t->right == NULL)); } // Prints the first non-matching leaf node in // two trees if it exists, else prints nothing. void findFirstUnmatch(Node *root1, Node *root2) { // If any of the tree is empty if (root1 == NULL || root2 == NULL) return ; // Create two stacks for preorder traversals stack<Node*> s1, s2; s1.push(root1); s2.push(root2); while (!s1.empty() || !s2.empty()) { // If traversal of one tree is over // and other tree still has nodes. if (s1.empty() || s2.empty() ) return ; // Do iterative traversal of first tree // and find first lead node in it as "temp1" Node *temp1 = s1.top(); s1.pop(); while (temp1 && !isLeaf(temp1)) { // pushing right childfirst so that // left child comes first while popping. s1.push(temp1->right); s1.push(temp1->left); temp1 = s1.top(); s1.pop(); } // Do iterative traversal of second tree // and find first lead node in it as "temp2" Node * temp2 = s2.top(); s2.pop(); while (temp2 && !isLeaf(temp2)) { s2.push(temp2->right); s2.push(temp2->left); temp2 = s2.top(); s2.pop(); } // If we found leaves in both trees if (temp1 != NULL && temp2 != NULL ) { if (temp1->data != temp2->data ) { cout << "First non matching leaves : " << temp1->data << " " << temp2->data << endl; return ; } } } } // Driver code int main() { struct Node *root1 = newNode(5); root1->left = newNode(2); root1->right = newNode(7); root1->left->left = newNode(10); root1->left->right = newNode(11); struct Node * root2 = newNode(6); root2->left = newNode(10); root2->right = newNode(15); findFirstUnmatch(root1,root2); return 0; } |
Java
// Java program to find first leaves that are // not same. import java.util.*; class GfG { // Tree node static class Node { int data; Node left, right; } // Utility method to create a new node static Node newNode( int x) { Node temp = new Node(); temp.data = x; temp.left = null ; temp.right = null ; return temp; } static boolean isLeaf(Node t) { return ((t.left == null ) && (t.right == null )); } // Prints the first non-matching leaf node in // two trees if it exists, else prints nothing. static void findFirstUnmatch(Node root1, Node root2) { // If any of the tree is empty if (root1 == null || root2 == null ) return ; // Create two stacks for preorder traversals Stack<Node> s1 = new Stack<Node> (); Stack<Node> s2 = new Stack<Node> (); s1.push(root1); s2.push(root2); while (!s1.isEmpty() || !s2.isEmpty()) { // If traversal of one tree is over // and other tree still has nodes. if (s1.isEmpty() || s2.isEmpty() ) return ; // Do iterative traversal of first tree // and find first lead node in it as "temp1" Node temp1 = s1.peek(); s1.pop(); while (temp1 != null && isLeaf(temp1) != true ) { // pushing right childfirst so that // left child comes first while popping. s1.push(temp1.right); s1.push(temp1.left); temp1 = s1.peek(); s1.pop(); } // Do iterative traversal of second tree // and find first lead node in it as "temp2" Node temp2 = s2.peek(); s2.pop(); while (temp2 != null && isLeaf(temp2) != true ) { s2.push(temp2.right); s2.push(temp2.left); temp2 = s2.peek(); s2.pop(); } // If we found leaves in both trees if (temp1 != null && temp2 != null ) { if (temp1.data != temp2.data ) { System.out.println(temp1.data+ " " +temp2.data); return ; } } } } // Driver code public static void main(String[] args) { Node root1 = newNode( 5 ); root1.left = newNode( 2 ); root1.right = newNode( 7 ); root1.left.left = newNode( 10 ); root1.left.right = newNode( 11 ); Node root2 = newNode( 6 ); root2.left = newNode( 10 ); root2.right = newNode( 15 ); findFirstUnmatch(root1,root2); } } |
Python3
# Python3 program to find first leaves # that are not same. # Tree Node # Utility function to create a # new tree Node class newNode: def __init__( self , data): self .data = data self .left = self .right = None def isLeaf(t): return ((t.left = = None ) and (t.right = = None )) # Prints the first non-matching leaf node in # two trees if it exists, else prints nothing. def findFirstUnmatch(root1, root2) : # If any of the tree is empty if (root1 = = None or root2 = = None ) : return # Create two stacks for preorder # traversals s1 = [] s2 = [] s1.insert( 0 , root1) s2.insert( 0 , root2) while ( len (s1) or len (s2)) : # If traversal of one tree is over # and other tree still has nodes. if ( len (s1) = = 0 or len (s2) = = 0 ) : return # Do iterative traversal of first # tree and find first lead node # in it as "temp1" temp1 = s1[ 0 ] s1.pop( 0 ) while (temp1 and not isLeaf(temp1)) : # pushing right childfirst so that # left child comes first while popping. s1.insert( 0 , temp1.right) s1.insert( 0 , temp1.left) temp1 = s1[ 0 ] s1.pop( 0 ) # Do iterative traversal of second tree # and find first lead node in it as "temp2" temp2 = s2[ 0 ] s2.pop( 0 ) while (temp2 and not isLeaf(temp2)) : s2.insert( 0 , temp2.right) s2.insert( 0 , temp2.left) temp2 = s2[ 0 ] s2.pop( 0 ) # If we found leaves in both trees if (temp1 ! = None and temp2 ! = None ) : if (temp1.data ! = temp2.data ) : print ( "First non matching leaves :" , temp1.data, "", temp2.data ) return # Driver Code if __name__ = = '__main__' : root1 = newNode( 5 ) root1.left = newNode( 2 ) root1.right = newNode( 7 ) root1.left.left = newNode( 10 ) root1.left.right = newNode( 11 ) root2 = newNode( 6 ) root2.left = newNode( 10 ) root2.right = newNode( 15 ) findFirstUnmatch(root1,root2) # This code is contributed by # SHUBHAMSINGH10 |
C#
// C# program to find first leaves that are // not same. using System; using System.Collections.Generic; class GfG { // Tree node public class Node { public int data; public Node left, right; } // Utility method to create a new node static Node newNode( int x) { Node temp = new Node(); temp.data = x; temp.left = null ; temp.right = null ; return temp; } static bool isLeaf(Node t) { return ((t.left == null ) && (t.right == null )); } // Prints the first non-matching leaf node in // two trees if it exists, else prints nothing. static void findFirstUnmatch(Node root1, Node root2) { // If any of the tree is empty if (root1 == null || root2 == null ) return ; // Create two stacks for preorder traversals Stack<Node> s1 = new Stack<Node> (); Stack<Node> s2 = new Stack<Node> (); s1.Push(root1); s2.Push(root2); while (s1.Count != 0 || s2.Count != 0) { // If traversal of one tree is over // and other tree still has nodes. if (s1.Count == 0 || s2.Count == 0 ) return ; // Do iterative traversal of first tree // and find first lead node in it as "temp1" Node temp1 = s1.Peek(); s1.Pop(); while (temp1 != null && isLeaf(temp1) != true ) { // pushing right childfirst so that // left child comes first while popping. s1.Push(temp1.right); s1.Push(temp1.left); temp1 = s1.Peek(); s1.Pop(); } // Do iterative traversal of second tree // and find first lead node in it as "temp2" Node temp2 = s2.Peek(); s2.Pop(); while (temp2 != null && isLeaf(temp2) != true ) { s2.Push(temp2.right); s2.Push(temp2.left); temp2 = s2.Peek(); s2.Pop(); } // If we found leaves in both trees if (temp1 != null && temp2 != null ) { if (temp1.data != temp2.data ) { Console.WriteLine(temp1.data + " " + temp2.data); return ; } } } } // Driver code public static void Main(String[] args) { Node root1 = newNode(5); root1.left = newNode(2); root1.right = newNode(7); root1.left.left = newNode(10); root1.left.right = newNode(11); Node root2 = newNode(6); root2.left = newNode(10); root2.right = newNode(15); findFirstUnmatch(root1,root2); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find first leaves that are // not same. // Tree node class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } } // Utility method to create a new node function newNode(x) { var temp = new Node(); temp.data = x; temp.left = null ; temp.right = null ; return temp; } function isLeaf(t) { return ((t.left == null ) && (t.right == null )); } // Prints the first non-matching leaf node in // two trees if it exists, else prints nothing. function findFirstUnmatch(root1, root2) { // If any of the tree is empty if (root1 == null || root2 == null ) return ; // Create two stacks for preorder traversals var s1 = []; var s2 = []; s1.push(root1); s2.push(root2); while (s1.length != 0 || s2.length != 0) { // If traversal of one tree is over // and other tree still has nodes. if (s1.length == 0 || s2.length == 0 ) return ; // Do iterative traversal of first tree // and find first lead node in it as "temp1" var temp1 = s1[s1.length-1]; s1.pop(); while (temp1 != null && isLeaf(temp1) != true ) { // pushing right childfirst so that // left child comes first while popping. s1.push(temp1.right); s1.push(temp1.left); temp1 = s1[s1.length-1]; s1.pop(); } // Do iterative traversal of second tree // and find first lead node in it as "temp2" var temp2 = s2[s2.length-1]; s2.pop(); while (temp2 != null && isLeaf(temp2) != true ) { s2.push(temp2.right); s2.push(temp2.left); temp2 = s2[s2.length-1]; s2.pop(); } // If we found leaves in both trees if (temp1 != null && temp2 != null ) { if (temp1.data != temp2.data ) { document.write( "First non matching leaves : " + temp1.data + " " + temp2.data); return ; } } } } // Driver code var root1 = newNode(5); root1.left = newNode(2); root1.right = newNode(7); root1.left.left = newNode(10); root1.left.right = newNode(11); var root2 = newNode(6); root2.left = newNode(10); root2.right = newNode(15); findFirstUnmatch(root1,root2); </script> |
First non matching leaves : 11 15
Time Complexity: O(n1+n2) where n1 and n2 are the total number of nodes in the two trees
Auxiliary Space: O(h1 + h2) where h1 and h2 are the heights of the two trees