Is it possible to compare two binary trees in less than O(n log n) time?

Question

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?

Answer 1

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.