Solving Binary Tree Algorithms Using Recursion and Queues

Today's algorithm is the Same Tree Problem:

Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

For example, if you were given the trees

   1            1
 /   \        /   \
2     3      2     3

the function should return true, since these trees are structurally the same and the nodes have the same value. But if you were given the trees

   1            1
 /   \        /   \
2     3      4     8

the function should return false. Although the trees are structurally the same, they do not have the same values.

Before discussing how to approach and solve this problem, it's valuable to talk about what binary trees are. A binary tree is a data structure containing nodes. The topmost node is called the root. Each node has a value, as well as a right reference and a left reference. You can learn more about binary trees here.

In this problem, we want to check each node in both of the inputted binary trees and to see if their values are equal to one another, and if the structure is the same. In this post, I'll go over two ways to approach and solve this problem with JavaScript: using recursion and using a queue.

Approach #1: Recursion

To solve this problem using recursion, we want to check each node in both trees. If those nodes are not equal, or if one node is null (meaning it doesn't exist) and the other one is not null, then we know the trees are not identical. Otherwise, we'll check the left nodes and right nodes, and keep going down the trees until we reach null on both trees. If the trees are null at the same point, and at no point were the node's values unequal, then we can return true.

Coding the first approach

To start a recursive solution, we have to consider base cases. If the nodes of both trees are null at the same point, then we can return true. If the node of one tree is null, but the other tree is not null, then we know the trees are unequal, so we can return false.

function isSameTree1(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    //...
}

If the values at the nodes are unequal, we know the trees are not identical, so we can return false. We can check the value of the nodes with .val because that was given in the Leetcode problem.

function isSameTree1(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;
    //...
}

The last element of the recursive solution is to actually make the recursive calls. We want to check both the right and the left nodes of both trees. That means we'll want to make two recursive calls to the function, one for the nodes on the left, accessed using .left, and one for the nodes on the right, accessed using .right. We'll separate these calls with the and operator, &&, because the nodes have to be equal on both the right and the left for the trees to be equal.

function isSameTree1(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;
    return isSameTree1(p.left, q.left) && isSameTree(p.right, q.right);
}

Approach #2: Queues

To solve this problem using queues, we want to create a queue for both of the inputted trees. A queue is a data structure that uses first in, first out logic: the first node to get added to the list is the first one to be removed from the list. This structure is useful when working with trees because we can add nodes in a systematic way, and check them systematically as well.

In this problem, we'll check the first node from both queues to see if their values are different. If so, we know the trees aren't identical, so we can return false. Otherwise, we'll add the left and right nodes of both trees to the respective queues. If one tree has a left node, and the other one doesn't, then we know the trees aren't identical, so we can return false (the same is true in the case of right nodes). If we check every left and right node in both trees, they were identical every time, then we know the trees are identical.

Coding the second approach

We'll start the second solution with the same base cases as above: if both tree's roots are null, then the trees are the same, and we can return true. If one tree's root is null, but the other isn't, then the trees are different, and we can return false.

function isSameTree2(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;

    //...
}

We'll want to create two queues, one for each tree. In JavaScript, we can do that by creating an array, and placing the root node in it.

function isSameTree2(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;

    let queueP = [p]
    let queueQ = [q]

   //...
}

Now, we'll set up a while loop -- as long as there are still values in both queues to check, we'll keep checking the values. Inside the while loop, we'll set up two variables -- the current node in queueP that we're checking, and the current node in queueQ that we're checking. We can access these variables using .shift(), which removes the first element from an array.

function isSameTree2(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;

    let queueP = [p]
    let queueQ = [q]

    while (queueP.length && queueQ.length) {
        const currentP = queueP.shift();
        const currentQ = queueQ.shift();
        //...
    }
    //...
}

If currentP and currentQ have different values, we can return false.

We want to check if there are nodes to the left of the current nodes we're checking in both trees. If there are nodes to the left of both currentP and currentQ, then we'll push those left nodes to the respective queues. If one tree has a node to the left, but the other tree doesn't, that means their structures are not the same, so we can return false.

function isSameTree2(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;

    let queueP = [p]
    let queueQ = [q]

    while (queueP.length && queueQ.length) {
        const currentP = queueP.shift();
        const currentQ = queueQ.shift();
        if (currentP.val !== currentQ.val) return false;

        if (currentP.left && currentQ.left) {
            queueP.push(currentP.left)
            queueQ.push(currentQ.left)
        } else if (currentP.left || currentQ.left) return false;

        //...
    }
    //...
}

We can do the same for the right nodes -- if both currentP and currentQ have right nodes, then we can push them to their respective queues. If one tree has a right node, and the other one does not, we can return false.

This while loop will keep checking the nodes as long as new nodes are in the queues. If every node has been added to the queues and checked in the loop, and false was never returned, then we know the trees are identical, so we can return true.

function isSameTree2(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;

    let queueP = [p]
    let queueQ = [q]

    while (queueP.length && queueQ.length) {
        const currentP = queueP.shift();
        const currentQ = queueQ.shift();
        if (currentP.val !== currentQ.val) return false;

        if (currentP.left && currentQ.left) {
            queueP.push(currentP.left)
            queueQ.push(currentQ.left)
        } else if (currentP.left || currentQ.left) return false;

        if (currentP.right && currentQ.right) {
            queueP.push(currentP.right)
            queueQ.push(currentQ.right)
        } else if (currentP.right || currentP.right) return false;
    }
    return true;
}

Let me know in the comments if you have questions or other solutions to this problem!