Cdtrjyty

I wrote a java routine to compare 2 binary trees. I am looking for better algorithms that run in less time.

 public class TreeNode {

  int val;

  TreeNode left;

  TreeNode right;

  TreeNode(int x) { val = x; }

 }



 class Solution {

  public boolean isSameTree(TreeNode p, TreeNode q) {



    if  ( p == null && q==null)

        return true;



    if (p == null || q == null) 

        return false;



    if ( (p.val == q.val) && isSameTree(p.left, q.left) && 

      isSameTree(p.right, q.right))

        return true;

    else 

        return false;  

   }   

  }

My code takes O(n log n) time.

How to approach reducing the time required?

The current runtime of your approach is actually O(n), where n should be the number of nodes of the tree with lesser(or if they're equal) nodes.

Also, note to compare all the values of a data structure you would have to visit all of them and that is the runtime you could achieve and not reduce further. In the current case, at the worst, you would have to visit all the nodes of the smaller tree and hence O(n).

Hence any other approach though might help you with conditional optimization, your current solution has an optimal runtime which cannot be reduced further.

Time complexity of above solution is O(n + m) where m and n are number of nodes in two trees.

 import java.util.*; 

class GfG { 



// A Binary Tree Node  

static class Node  

{  

    int data;  

    Node left, right;  

} 



// Iterative method to find height of Bianry Tree  

static boolean areIdentical(Node root1, Node root2)  

{  

    // Return true if both trees are empty  

    if (root1 != null && root2 != null)  return true;  



    // Return false if one is empty and other is not  

    if (root1 != null || root2 != null) return false;  



    // Create an empty queues for simultaneous traversals  

    Queue<Node > q1 = new LinkedList<Node> (); 

    Queue<Node>  q2 = new LinkedList<Node> ();  



    // Enqueue Roots of trees in respective queues  

    q1.add(root1);  

    q2.add(root2);  



    while (!q1.isEmpty() && !q2.isEmpty())  

    {  

        // Get front nodes and compare them  

        Node n1 = q1.peek();  

        Node n2 = q2.peek();  



        if (n1.data != n2.data)  

        return false;  



        // Remove front nodes from queues  

        q1.remove(); 

        q2.remove();  



        /* Enqueue left children of both nodes */

        if (n1.left != null && n2.left != null)  

        {  

            q1.add(n1.left);  

            q2.add(n2.left);  

        }  



        // If one left child is empty and other is not  

        else if (n1.left != null || n2.left != null)  

            return false;  



        // Right child code (Similar to left child code)  

        if (n1.right != null && n2.right != null)  

        {  

            q1.add(n1.right);  

            q2.add(n2.right);  

        }  

        else if (n1.right != null || n2.right != null)  

            return false;  

    }  



    return true;  

}  



// Utility function to create a new tree node  

static Node newNode(int data)  

{  

    Node temp = new Node();  

    temp.data = data;  

    temp.left = null; 

    temp.right = null;  

    return temp;  

}  



// Driver program to test above functions  

public static void main(String args)  

{  

    Node root1 = newNode(1);  

    root1.left = newNode(2);  

    root1.right = newNode(3);  

    root1.left.left = newNode(4);  

    root1.left.right = newNode(5);  



    Node root2 = newNode(1);  

    root2.left = newNode(2);  

    root2.right = newNode(3);  

    root2.left.left = newNode(4);  

    root2.left.right = newNode(5);  



    if(areIdentical(root1, root2) == true) 

    System.out.println("Yes"); 

    else

    System.out.println("No"); 

} 

}