C++ program to check if leaf traversal of two Binary Trees is same

By Himanshu Baranwal

In this tutorial we will learn how to tell if leaf traversal of two binary trees is the same or not.
Leaf traversal of a tree means traversing each leaf of the binary tree from the left direction to the right sequentially.
Consider two binary trees with the following nodes:

1)      3                                      2)     7
       / \                                          /   \
      2   4                                        5     4
         /  \                                     /    /   \
        6    7                                   2    1     9
           /  \                                      / \   /
          8    9                                    6   8 11
              /
             11

For the above trees the leaf traversal are same i.e.
For 1) tree the leaf traversal is: 2 6 8 11
For 2) tree the leaf traversal is: 2 6 8 11 
Hence, it is same for both the trees.

Algorithm:

Empty stacks st1 and st2 are used for iterative traversals of tree1 and tree2.
Both stacks are initially pushed with the root of the respective trees.
A temporary variable t is used for storing current leaf nodes of tree1 and tree2.
t1 = (root of tree1)
t2 = (root of tree2)

We traverse the whole tree making use of stacks st1 and st2.

while (st1 is not empty or st2 is not empty) 
{
// when excess leaves are present in one of the tree
if (if one of the stacks are empty) 
return false
// get next leaf node in tree1 
t1 = st1.pop()
while (t1 is not leaf node) 
{
push the right child to st1 
push the left child to st1
}
get next leaf node in tree2 
t2 = st2.pop()
while (t2 is not leaf node) 
{
push the right child to st2 
push the left child to st2
}
// If leaves do not match return false
if (t1 != t2) 
return false
}

Return true if all leaves are matched.

This can be illustrated using the following example:

#include<bits/stdc++.h> 
using namespace std; 
  
// Binary Tree Node Structure
struct Node 
{ 
    int key; 
    Node* left; 
    Node* right;
    Node()
    {
     left=NULL;right=NULL;
     }	
}; 
  
// new node creation with given key 
Node* nNode(int data) 
{ 
    Node* temp = new Node; 
    temp->key = data; 
    return temp;  
} 
  
// function checking if a given node is leaf node or not. 
bool is_Leaf(Node* root) 
{ 
    if(root == NULL) 
        return false; 
    if(!root->left && !root->right) 
        return true; 
    return false; 
} 
  
 //function that returns true if leaf traversals are same
// else false. 
bool is_TraversalSame(Node* root1, Node* root2) 
{ 
    stack<Node*> st1; 
    stack<Node*> st2; 
      
    //pushing root1 to empty stack st1. 
    st1.push(root1); 
      
    //pushing root2 to empty stack st2. 
    st2.push(root2); 
      
	  //loop performs the operation until both stack becomes empty
    while(!st1.empty() || !st2.empty()) 
    { 
        // this means one of the stacks has extra leaf nodes 
        if(st1.empty() || st2.empty()) 
            return false; 
              
        Node* t1 = st1.top(); 
        st1.pop(); 
        while(t1 != NULL && !is_Leaf(t1)) 
        { 
            // Pushing right child if exists 
            if(t1->right) 
                st1.push(t1->right); 
                  
            // Pushing left child if exists 
            if(t1->left) 
                st1.push(t1->left); 
                  
            //since it is a stack we push right child first then left child
			//so that left child could be taken out first
            t1 = st1.top(); 
            st1.pop(); 
        } 
          
        Node* t2 = st2.top(); 
        st2.pop(); 
        while(t2 != NULL && !is_Leaf(t2)) 
        { 
            // Pushing right child if exists 
            if(t2->right) 
                st2.push(t2->right); 
                  
            // Pushing left child if exists 
            if(t2->left) 
                st2.push(t2->left); 
            t2 = st2.top(); 
            st2.pop(); 
        } 
          
        if(!t1 && t2) 
            return false; 
        if(t1 && !t2) 
            return false; 
        if(t1 && t2) 
        { 
            return t1->key == t2->key; 
        } 
    } 
      
    // At the end of loop all leaves are matched hence returned true
    return true; 
} 
int main() 
{ 
    Node* rt1 = nNode(3); 
    rt1->left = nNode(2); 
    rt1->right = nNode(4); 
    rt1->right->left = nNode(6); 
    rt1->right->right = nNode(7); 
    rt1->right->right->left = nNode(8); 
	rt1->right->right->right = nNode(9);
    rt1->right->right->right->left = nNode(11); 	
      
    Node* rt2 = nNode(7); 
    rt2->left = nNode(5); 
    rt2->right = nNode(4); 
    rt2->left->left = nNode(2); 
    rt2->right->left = nNode(1); 
    rt2->right->right = nNode(9);
    rt2->right->left->left = nNode(6); 	
	rt2->right->left->right = nNode(8);
    rt2->right->right->left = nNode(11); 	
      
    if(is_TraversalSame(rt1, rt2)) 
        cout << "Leaf traversal is same :) "; 
    else
        cout << "Leaf traversal is not same :( "; 
    return 0; 
}

The output of the following program is:
Leaf traversal is same :)

The time complexity of the following program is O(n) where n is the number of nodes of the three having more nodes. And the auxiliary space required is O(H1+H2); where H1 is the height of the first tree and H2 is the height of the second tree.
That’s all for this tutorial.
I hope it helps.

Also read:

Leave a Reply Cancel reply