Leetcode Same Tree

Same Tree Problem

This was an easy level problem, but my first problem which used a tree. You’re given two trees which are represented by arrays. You have to determine if the trees are exactly the same, with the same structure. Because you have to confirm the tree’s structure, that let me know that I needed a Depth-First Search algorithm to solve the problem.

Here’s the given examples. There are a few images to illustrate the trees. The first number is the root of the tree, and the next number is the left child, then the right child. When a null is shown in an array, it means that the left child is a nullptr. This value of NULL ended up being a problem for me because a null in the input sets a node value as 0 due to the TreeNode initialization. So, in these cases I pushed a value of 10⁴ + 1 because a constraint was given as: -10⁴ <= node.val <= 10⁴

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

Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false

Depth-First Search

A depth-first search is an algorithm which can be used to record the structure of a tree. It prioritizes going down a tree branch instead of going down one level at a time (a breadth-first search). It is best to implement with recursion. There are 4 major steps to implement recursion.

1. The first step is a base case, where you have a condition to end recursion.
   • In this problem, our base case is when we get to a node with a value of null.
   • Because the way they represent the tree with the array input, I had to push an out of range value instead of null at the basecase
2. The next step is is a pre-recursion step, where if you have to do something before you start recursing you do it!
   • Here, we record the current node’s value and push it into a vector. We use it later.
3. Now is the recursion step where we recurse and run all of the same code as above until we get to the base case.
   • So here, we go left first until we reach a the null pointers and record each step.
   • Once we get to the base case, we return up and go right, doing the same thing.
4. Finally, we have a post step, which you do something if you need to after recursion is all done.
   • We don’t have a post step here, besides returning to the function that called us.

Here’s the code in C++, hopefully the explaination above and the comments help explain everything.

/*  Definition for a binary tree node. */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : 
        val(x), left(left), right(right) {}
};

#include<vector>
using namespace std;

void walk(TreeNode* node, vector<int>& path) {
    // recursive depth-first search
    // base case: reach a null node
    if (!node) {
        // null => 0 in TreeNode initialization which is frustrating
        path.push_back(10001); // -10^4 <= node.val <= 10^4
        return;
    }
    // pre: visit the node
    path.push_back(node->val);
    // recurse: walk left first
    walk(node->left, path);
    walk(node->right, path);
    // post: none
    return;
}

bool isSameTree(TreeNode* p, TreeNode* q) {
    // create vectors to hold the values of the trees
    vector<int> p_path, q_path;

    walk(p,p_path);
    walk(q,q_path);

    return (p_path == q_path) ? true : false;
}

A Better Solution

While I was looking at other answers to the question, I realized how I could improve my approach. Instead of having to generate two lists to compare the trees, I can just compare as I walk the lists. This would mean that I do the same depth-first traversal on both trees at the same time. When I get to a node, the base cases compare if the nodes are identical; i.e., I check if I’m at a null node on both trees and return up a level in the first case. If I’m at a null node on one tree and not the other or if the values are not the same, I return false all the way up the recursion stack.

So, here’s the implementation, which is much shorter. Surprisingly though, this took the same amount of memory which I guess means that the tree structures are just so much larger than any vector that I made in the previous implementation. This also negated the need to push an arbitrary value to my list if I wanted to express that I reached a nullptr.

bool isSameTree(TreeNode* p, TreeNode* q) {
    // base cases: 1, both trees' branches end simultaneously return true
    if (!p && !q) {
        return true;
    }
    // 2, if only one node is a nullptr or the values don't match return false
    if ((!p || !q) || (p->val != q->val)) {
        return false;
    }
    // no pre or post steps, just recurse
    bool l = isSameTree(p->left,q->left); // keep track of t/f while coming up
    bool r = isSameTree(p->right,q->right);
    // when both sides of a branch have been checked; any 1 false returns false
    return (l && r) ? true : false;
}