How to Determine 2 Binary Trees are Identical, Using Javascript

#javascript #beginners #webdev #tutorial

Introduction

Here identical means both structure and values are in the same position.

To achieve this we need to use DFS algorithm so it will check depth as well.

This can't be achieved using BFS Algo.

So here I am using In Order Traversal to get the result.

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

let root1, root2;

// left root right
const checkIdentical = (binaryTree1, binaryTree2) => {
    let tree = '';
    const helper = (root) => {
        if (root == null) {
            return tree;
        }
        helper(root.left);
        tree += root.data;
        helper(root.right);

        return tree;
    };

    const tree1 = helper(binaryTree1);
    tree = '';
    const tree2 = helper(binaryTree2);
    if (tree1 === tree2) {
        console.log('Both are identical');
    } else {
        console.log('Not Identical');
    }

}

root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);

root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);
checkIdentical(root1, root2);

/*
Both are identical

*/

Feel free to reach out to me if you have any concerns

Top comments (6)

Dmitrii Paskhin • Aug 28 • Edited

Cool solution!

I just wanted to suggest a little enhance - this algorithm works only with primitive data structure, that can be stringified by JS properly, for supporting more complex data structures I'd suggest using some strigifier by default it can be simple JSON.stringify

But there has to be more detailed requirement of the task, though, I mean maybe we don't want to compare object data deeply and so on

Ashutosh Sarangi • Aug 28

Sounds great., Thank you

Dmitrii Paskhin • Aug 28

Yeah, you can go on and use a stash instead of a string and store in it different types of data and for comparison objects you can add a specific type field and you almost get reconciliation from ReactJS :)

Anyway, your solution is cool for your task requirements :) but I'd like to suggest your the last enhancement, I guess it'd be better to use helper function param for storing the tree variable

const helper = (root, tree = '') => {
  if (root == null) {
    return tree;
  }
  helper(root.left, tree);
  tree += root.data;
  helper(root.right, tree);

  return tree;
};