Solving Binary Tree Algorithms Using Recursion and Queues
Tags: javascript, codenewbie, recursion, queues
Published: 2020-07-13 18:27:21

Today's algorithm is the [Same Tree Problem](https://leetcode.com/problems/same-tree/):
> 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](https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html).

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.

```javascript
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.

```javascript
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.

```javascript
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`.

```javascript
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.

```javascript
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.

```javascript
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`.

```javascript
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`.

```javascript
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!