Find first non matching leaves in two binary trees | Java program to find first leaves that are not same . ; Tree node ; Utility method to create a new node ; Prints the first non - matching leaf node in two trees if it exists , else prints nothing . ; If any of the tree is empty ; Create two stacks for preorder traversals ; If traversal of one tree is over and other tree still has nodes . ; Do iterative traversal of first tree and find first lead node in it as " temp1" ; pushing right childfirst so that left child comes first while popping . ; Do iterative traversal of second tree and find first lead node in it as " temp2" ; If we found leaves in both trees ; Driver code
import java . util . * ; class GfG { static class Node { int data ; Node left , right ; } 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 ) ) ; } static void findFirstUnmatch ( Node root1 , Node root2 ) { if ( root1 == null root2 == null ) return ; Stack < Node > s1 = new Stack < Node > ( ) ; Stack < Node > s2 = new Stack < Node > ( ) ; s1 . push ( root1 ) ; s2 . push ( root2 ) ; while ( ! s1 . isEmpty ( ) || ! s2 . isEmpty ( ) ) { if ( s1 . isEmpty ( ) || s2 . isEmpty ( ) ) return ; Node temp1 = s1 . peek ( ) ; s1 . pop ( ) ; while ( temp1 != null && isLeaf ( temp1 ) != true ) { s1 . push ( temp1 . right ) ; s1 . push ( temp1 . left ) ; temp1 = s1 . peek ( ) ; s1 . pop ( ) ; } 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 ( temp1 != null && temp2 != null ) { if ( temp1 . data != temp2 . data ) { System . out . println ( temp1 . data + " ▁ " + temp2 . data ) ; return ; } } } } 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 ) ; } }