Check if leaf traversal of two Binary Trees is same ? | C ++ code to check if leaf traversals of two Binary Trees are same or not . ; Binary Tree Node ; Returns new Node with data as input to below function . ; checks if a given node is leaf or not . ; iterative function . returns true if leaf traversals are same , else false . ; Create empty stacks . These stacks are going to be used for iterative traversals . ; loop until either of stacks are non - empty . ; this means one of the stacks has extra leaves , hence return false . ; Push right and left children of temp1 . Note that right child is inserted before left ; same for tree2 ; If one is null and other is not , then return false ; If both are not null and data is not same return false ; all leaves are matched ; Driver Code ; Let us create trees in above example 1
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left ; Node * right ; } ; Node * newNode ( int d ) { Node * temp = new Node ; temp -> data = d ; temp -> left = NULL ; temp -> right = NULL ; return temp ; } bool isLeaf ( Node * root ) { if ( root == NULL ) return false ; if ( ! root -> left && ! root -> right ) return true ; return false ; } bool isSame ( Node * root1 , Node * root2 ) { stack < Node * > s1 ; stack < Node * > s2 ; s1 . push ( root1 ) ; s2 . push ( root2 ) ; while ( ! s1 . empty ( ) || ! s2 . empty ( ) ) { if ( s1 . empty ( ) || s2 . empty ( ) ) return false ; Node * temp1 = s1 . top ( ) ; s1 . pop ( ) ; while ( temp1 != NULL && ! isLeaf ( temp1 ) ) { if ( temp1 -> right ) s1 . push ( temp1 -> right ) ; if ( temp1 -> left ) s1 . push ( temp1 -> left ) ; temp1 = s1 . top ( ) ; s1 . pop ( ) ; } Node * temp2 = s2 . top ( ) ; s2 . pop ( ) ; while ( temp2 != NULL && ! isLeaf ( temp2 ) ) { if ( temp2 -> right ) s2 . push ( temp2 -> right ) ; if ( temp2 -> left ) s2 . push ( temp2 -> left ) ; temp2 = s2 . top ( ) ; s2 . pop ( ) ; } if ( ! temp1 && temp2 ) return false ; if ( temp1 && ! temp2 ) return false ; if ( temp1 && temp2 ) { return temp1 -> data == temp2 -> data ; } } return true ; } int main ( ) { Node * root1 = newNode ( 1 ) ; root1 -> left = newNode ( 2 ) ; root1 -> right = newNode ( 3 ) ; root1 -> left -> left = newNode ( 4 ) ; root1 -> right -> left = newNode ( 6 ) ; root1 -> right -> right = newNode ( 7 ) ; Node * root2 = newNode ( 0 ) ; root2 -> left = newNode ( 1 ) ; root2 -> right = newNode ( 5 ) ; root2 -> left -> right = newNode ( 4 ) ; root2 -> right -> left = newNode ( 6 ) ; root2 -> right -> right = newNode ( 7 ) ; if ( isSame ( root1 , root2 ) ) cout << " Same " ; else cout << " Not ▁ Same " ; return 0 ; }