https://leetcode.com/problems/same-tree/
For this problem, we are given two trees and must evaluate if they are structurally identical and that the nodes have the same value. That is the only way they can be the same tree.
The biggest gotcha of this problem is if we should assert if they are the same or different at every node. The key to that is that if they are the same, then you simply keep going down the same branch on both respective trees and only asserting if they are different.
The only time two branches are the same is if you've actually reached the end without anything causing you to stop. The cases that can cause you to stop include:
Keeping that in mind, we can utilize recursion to solve this problem.
Space: O(n)
The worst case is if all trees only have one child, then the depth of our recursion is O(n).
If our tree is perfectly balanced, then our space complexity would be O(log(n)).
Time: O(n)
Each node is visited at most once.
/**
* 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) {
if (p === null && q === null) {
return true
} else if (!p || !q || (p.val !== p.val)) {
return false
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};