Compare binary tree in javascript

Comparing two binary tree means comparing to root, left & right nodes. If you know tree traversal, then this will be easy for you. If not, i will reommend to please read this article - Binary tree & traversal.

Ok , so let’s create a compare function which will take two tree and returns true if equal & false if not.

function compare(tree1, tree2) {
    if (tree1.root.data != tree2.root.data) {
        return false;
    }
    //left
    const checkInLeft = (left1, left2) => {
        if (left1 == null || left2 == null) {
            if ((left1 && !left2) || (!left1 && left2)) {
                return false;
            }
            return true;
        }
        if (left1.data != left2.data) {
            return false;
        }
        return checkInLeft(left1.left, left2.left);
    }
    const checkInRight = (right1, right2) => {
        if (right1 == null || right2 == null) {
            if ((right1 && !right2) || (!right1 && right2)) {
                return false;
            }
            return true;
        }
        if (right1.data !== right2.data) {
            return false;
        }
        return checkInRight(right1.right, right2.right);
    }
    return checkInLeft(tree1.root.left, tree2.root.left) &&    checkInRight(tree1.root.right, tree2.root.right);
}

So in the above program -

• We first check for root node
• We check recursively for left side of tree
• We check recursively for right side of tree

Now, let’s write complete code —

class Node {
    constructor(value) {
        this.data = value;
    }
}
class BinaryTree {
    addLeft(value) {
        const node = new Node(value);
        if (this.root == null) {
            this.root = node;
        } else {
            let current = this.root;
            while (current.left != null) {
                current = current.left;
            }
            current.left = node;
        }
    }
    addRight(value) {
        const node = new Node(value);
        if (this.root == null) {
            this.root = node;
        } else {
            let current = this.root;
            while (current.right != null) {
                current = current.right;
            }
            current.right = node;
        }
    }
}
function compare(tree1, tree2) {
    if (tree1.root.data != tree2.root.data) {
        return false;
    }
    //left
    const checkInLeft = (left1, left2) => {
        if (left1 == null || left2 == null) {
            if ((left1 && !left2) || (!left1 && left2)) {
                return false;
            }
            return true;
        }
        if (left1.data != left2.data) {
            return false;
        }
        return checkInLeft(left1.left, left2.left);
    }
    const checkInRight = (right1, right2) => {
        if (right1 == null || right2 == null) {
            if ((right1 && !right2) || (!right1 && right2)) {
                return false;
            }
            return true;
        }
        if (right1.data !== right2.data) {
            return false;
        }
        return checkInRight(right1.right, right2.right);
    }
    return checkInLeft(tree1.root.left, tree2.root.left) && checkInRight(tree1.root.right, tree2.root.right);
}
const tree1 = new BinaryTree();
tree1.addLeft(5);
tree1.addLeft(10);
tree1.addRight(15);
tree1.addRight(25);
const tree2 = new BinaryTree();
tree2.addLeft(5);
tree2.addLeft(10);
tree2.addRight(15);
console.log("is equal", compare(tree1, tree1)); // true
console.log("is equal", compare(tree1, tree2)); // false

If you have any question/suggestion, feel free to drop a comment. Don’t forget to share the article with your friends.