Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Identical Trees (Main Thread)

Here is the interview question prompt, presented for reference.

Can you write a function to see if two binary trees are identical?

   1         1
  / \       / \
 2   3     2   3

The above two trees share the same structure in terms of shape and location of each parent nodes' children.

Additionally, each corresponding nodes at every position has the exact same value. Thus, the above is consideredidentical.

The below two are not identical, because we are missing a child node.

   1         1
  / \       / 
 1   3     3

The definition of a tree node is as follows:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

Constraints

  • Number of vertices in both the trees <= 100000
  • The trees can also be null
  • The values of the vertices in the tree will be between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked over 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Identical Trees.

Ray Commented on Jan 27, 2021:
js
function identicalTrees(tree1, tree2) {
  if (tree1 === null && tree2 === null) {
    return true;
  }
  if (tree1 === null || tree2 === null) {
    return false;
  }
  if (tree1.val === tree2.val) {
    return (
      identicalTrees(tree1.left, tree2.left) &&
      identicalTrees(tree1.right, tree2.right)
    );
  }
  return false;
}

JavaScript doesn't have an Exclusive OR operator or function as far as I'm aware, but it does have a Bitwise XOR () function.

http://www.howtocreate.co.uk/xor.html

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_XOR

The || in JavaScript is a Logical OR which is also a short-circuit operator since

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Logical_OR

I'm confused now since the 2nd half of Logical OR (||) doesn't get evaluated at all if the first half (tree ===null) evaluates to True?

SNIPPET
These are alternative solutions:

function identicalTrees(tree1, tree2) {
  if ( !tree1 && !tree2 ) return true;
  if ( !tree1 || !tree2 || tree1.val !== tree2.val ) return false;

  return identicalTrees( tree1.left, tree2.left ) && identicalTrees( tree1.right, tree2.right );
}
SNIPPET
const identicalTrees = function(p, q) {
    if ( !( tree1 || tree2 ) ) { // both empty, null, or undefined
        return true;
    } else if( tree1 && tree2 && tree1.val === tree2.val) { // both defined
        return ( identicalTrees( tree1.left, tree2.left ) && identicalTrees( tree1.right, tree2.right ) );
    }  
    return false;
};
Rahat Zaman Commented on Feb 05, 2021:

Hi Ray,
Yes, you are exactly correct. Not only in Javascript, but also in C, C++, Java, Python and many other languages have this kind of optimization for expression evaluation. For example:
1. Second half of logical OR (||) will not get evaluated if first half returns true.
2. Second half of logical AND (&&) will not get evaluated if first half returns true.

This can be proved by the following boolean algebra:

TRUE || A = TRUE
FALSE &amp;&amp; A = FALSE

Where A is any boolean variable.

That is why we do not need to even look at the second expression if first one is enough to depict the result. I hope this will resolve your confusion.

Moreover, both of your solutions are very elegant. We have slightly updated the code to add your elegance in our solution.