CODEWITHSUNDEEP
javascriptalgorithmdata-structuresbinary-treebinary-search-tree
lasabahebwa
lasabahebwa

Reputation: 301

How do i write a function in JavaScript that compares two trees defined by TreeNodes a and b?

I'm trying to write a JavaScript function that compares two binary trees defined by TreeNodes a and b and returns true if they are equal in structure and in value and false otherwise.

for example example of comparing both values and structure of two binary trees

Given the following class:

class TreeNode {
  constructor(data, left=null, right=null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

Here is the code i tried writing so far comapring TreeNode a and b.

const binaryTreeCompare = (a, b) => {
  if(a==null && b==null){
    return true;
  }else if(a!=null && b!=null){
    return(
      a.data == b.data && binaryTreeCompare(a.left, b.left) && binaryTreeCompare(a.right, b.right)
    );
  }
    else return false;
}

I expected an ouput of either true or false but this is what i get:

ReferenceError: compare is not defined
    at Context.it (test.js:116:16)

Upvotes: 1

Views: 2906

Answers (2)

lasabahebwa
lasabahebwa

Reputation: 301

Solution to my own question after serious research is shown in the snippet below.

function compare(a, b){
  if (!a && !b) {
      return true;
   } else if (!a || !b) {
      return false;
   } else {
      return a.val === b.val && compare(a.left, b.left) && compare(a.right, b.right);
   }
}

Upvotes: 8

Tom
Tom

Reputation: 9137

One quick-and-dirty approach could be to define a canonical serialization for trees, and then compare them.

The simplest approach would be to JSON.stringify each tree. You'd need to implement a custom toJSON method for TreeNode.

class TreeNode {
  constructor(data, left=null, right=null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  toJSON() {
    return JSON.stringify({ data: this.data, left: this.left, right: this.right });
  }
}

Then, binaryTreeCompare becomes trivial.

EDIT: once you've defined a custom toJSON method on TreeNode, then binaryTreeCompare becomes this:

function binaryTreeCompare(a, b) {
    return JSON.stringify(a) === JSON.stringify(b)
}

However, the error message you report has nothing to do with your algorithm. It's hard to know for sure what the problem is, because the error message references something that doesn't appear in your sample code. I suspect your real code differs from the code you posted in a way that is critical to the problem.

Upvotes: 0

Related Questions