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

Hey guys, in this tutorial we are going to check if leaf traversal of two binary trees is same or not using Java Programming.
Leaf traversal is a traversing of a series of leaves of a given tree and follows the process of checking each leaf in a tree statistics structure exactly once and traversing of leaves is done from left to right.

For executing leaf traversal of both binary trees, we use iterative traversal in which,

  • we traverse both binary trees concurrently.
  • Found both tress’ leaf node.
  • At last, compare whether both leaf nodes are same or not.

 

Leaf traversal of two Binary Trees

In this, we use two arrays to store nodes of both trees simultaneously while traversing both trees from left to right until we reach the leaf node of both trees.

  • The node of one tree is stored in one array and another tree node store in another array while traversing.
  • If we reach the leaf node of one tree but not of another tree, return false which means “leaf traversal of both the trees is not the same”.
  • If we reach the leaf node of both trees, then compare their leaf nodes and if they match then that means “leaf traversal of both binary trees is the same”.

 

So, the expected auxiliary space of traversing both trees will be O(l1 + l2), where l1 and l2 are heights of both Binary Trees.
The expected time complexity of traversing both trees will be O(n).

 

import java.util.*;
import java.io.*;

class Tree
{
  int data;
  Tree right,left;

  Tree(int d)
  {
    data= d;
    right= null;
    left= null;
  }

  boolean isLeafNode()
  {
    return (right==null && left==null);
  }
}

class leafTraversal
{
  
  public static boolean check(Tree r1, Tree r2)
  {
    //stacks for iterative traversals.
    Stack<Tree> st1= new Stack<Tree>();
    Stack<Tree> st2= new Stack<Tree>();	


    //push root nodes in stacks
    st1.push(r1);
    st2.push(r2);
      
    //loop until one of the stack is not empty
    while(!st1.empty() || !st2.empty())
    {

      //if one of the stack is empty, return false
      if(st1.empty() || st2.empty())
      {		
        return false;
      }

      //pop out the node from stack and store in t1
      Tree t1= st1.pop();
      while(!t1.isLeafNode() && t1!=null)       //check whether this node store in t1 is leaf 
                                                //node or not
      {

        //if present then right node insert first into stack before left node
        if (t1.right != null) 
               	{
               		st1.push(t1.right); 
            	}

            	if (t1.left != null) 
               	{
               		st1.push(t1.left); 
            	}

            	t1 = st1.pop(); 
      }

      //pop out the node from another stack and store in t2 
      Tree t2= st2.pop();
      while(!t2.isLeafNode() && t2!=null)
      {
        if (t2.right != null) 
               	{
               		st2.push(t2.right); 
            	}

            	if (t2.left != null) 
               	{
               		st2.push(t2.left); 
            	}

            	t2 = st2.pop(); 
      }

      // if both are not null but their data are not equal, then return false
      if(t1 != null && t2 !=null)
      {
        if(t1.data != t2.data)
        {
          return false;
        }
      }

      // if one is null and other is not, then return false
      if(t1==null && t2!=null)
      {
        return false; 
      }

      if(t1!=null && t2==null)
      {
        return false;
      }
    }

    // if all leaves are matched
    return true;
  }


  public static void main(String ar[])
  {
    Tree root1= new Tree(0);
    root1.left= new Tree(2);
    root1.right= new Tree(5);
    root1.left.right= new Tree(7);
    root1.right.left= new Tree(9);
    root1.right.right= new Tree(3);

    Tree root2= new Tree(2);
    root2.left= new Tree(4);
    root2.right= new Tree(6);
    root2.left.left= new Tree(7);
    root2.left.right= new Tree(9);
    root2.right.right= new Tree(3);

    
    if(check(root1, root2))
    {
      System.out.println("Leaf traversal of two Binary Trees is same");
    }
    else
    {
      System.out.println("Leaf traversal of two Binary Trees is not same");
    }
  }
}

 

output:

Leaf traversal of two Binary Trees is same

 

You should also see this tutorial,

How to validate identifier using Regular Expression in Java

Singleton Design Pattern in Java

Leave a Reply

Your email address will not be published. Required fields are marked *