100. Same Tree 🚀

---

Solution Developed In:

The Question

For this article we will be covering Leetcode's '100. Same Tree' question. This question is rated as an Easy question.

Question:

Given the roots of two binary trees p and q, 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.

Example:

     1      1
    / \    / \
   2   3  2   3

Input: p = [1,2,3], q = [1,2,3]
Output: true

Explaining The Question

What we're being asked is to check if two binary trees are the same or not. Which mean's we're expected to compare all the values of the nodes from both trees in the same order.

Recommended Knowledge

1. Binary Tree
2. Depth First Search (Recursive)
3. Javascript Stack
4. Recursion

What do we know?

1. That we have 2 trees and we need to check that they're the same
2. The max number of nodes a tree can have is 100.

How we're going to do it:

1. We're going to do this recursively. Meaning, that at each node in the both trees, we're going to be visiting at one point. We do this by recalling the isSameTree function with the left or right pointers
2. We're going to go to each node in both trees at the same time. That is to say, in tree 1, when we go left, we also go left in tree 2. Until we reach the very end of that right tree. We will also do this with the right tree too.
3. Each time we visit a new node, we will make a check, are both nodes empty? In this case, both trees are empty and are at the end and thus correct.
4. Are any of the pointers null that aren't supposed to be? Meaning the mirror node isn't null? In this case, it's a invalid tree.
5. We then check the values. Are they not the same? Then it's a invalid tree
6. Repeat this until all nodes are exhausted, comparing that both the left and right trees are valid.

Big O Notation:

• Time Complexity: O(n) | Where n is equal to the number of nodes in both trees. | We visit every node in worst case
• Space Complexity: O(h) | Where h is the height of the tallest tree. This is within the Call Stack | In the worst case, a tree's number of nodes is it's height. Thus it's argued the real space complexity is O(n)

Leetcode Results:

See Submission Link:

• Runtime: 64 ms, faster than 84.15% of JavaScript online submissions for Same Tree.
• Memory Usage: 42.3 MB, less than 58.35% of JavaScript online submissions for Same Tree.

---

The Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val   = (val===undefined ? 0 : val)
 * this.left  = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    /* -------------------------------------------------------------------------- */
    /*                               100. Same Tree                               */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */


    /* ----------------------------- Solution Below ----------------------------- */

    // So both our trees current node is null
    // This mean's they both reached the end of the tree
    // at the same time without error
    if (p == null && q == null) {
        return true;
    }

    // One of the pointers are null when another is not
    // This mean's one of our pointers has traversed to a correct node
    // but another has reached the end of the list too early and thus
    // cannot be a valid mirror tree
    if ((p == null && q != null) || (q == null && p != null)) {
        return false;
    }

    // As we have moved nodes
    // Are they the same value?
    if (p.val != q.val) {
        return false;
    }

    // Get both left nodes
    // We will traverse the left nodes in a DFS fashion
    // to be able to compare both left nodes at the same time
    // So we move left at the same time on both trees.
    let good_lefts = isSameTree(p.left, q.left);

    // Get both right nodes
    // We will traverse the right nodes in a DFS fashion
    // to be able to compare both right nodes at the same time
    // So we move right at the same time on both trees.
    let good_rights = isSameTree(p.right, q.right);

    // So are both sides good?
    return good_lefts && good_rights;
};

Comments

[Samuel Hinchliffe 🚀]

Hey There 👋

---

Thank you for taking the time to look at my solution. I hope you found it interesting and useful.

If you're having difficulties understanding this solution or just need some clarity on a certain section of it. Please do not hesitate to contact me. We're all in this together and I'm happy to help. 😁

---

Contact me here:

[Elena Kazakova]

Thanks for the explanation! A little code highlighter would be nice)