DEV Community

Ashutosh Sarangi
Ashutosh Sarangi

Posted on

How to Determine 2 Binary Trees are Identical, Using Javascript

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

*/
Enter fullscreen mode Exit fullscreen mode

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

Top comments (6)

Collapse
 
dpaskhin profile image
Dmitrii Paskhin • 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

Collapse
 
ashutoshsarangi profile image
Ashutosh Sarangi

Sounds great., Thank you

Collapse
 
dpaskhin profile image
Dmitrii Paskhin

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;
};
Enter fullscreen mode Exit fullscreen mode
Collapse
 
razielrodrigues profile image
Raziel Rodrigues

I had a similar question during an interview and I was fucked up by this hahaha

Collapse
 
ashutoshsarangi profile image
Ashutosh Sarangi

ha ha , not anymore

Collapse
 
razielrodrigues profile image
Raziel Rodrigues

but man, im tired about those questions e_e i dont think this say you are a good developer or not but whatever