Same Binary Tree

Problem

Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.

Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.

Examples

Example 1:

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

Output: true

Example 2:

Input: p = [4,7], q = [4,null,7]

Output: false

Example 3:

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

Output: false

Constraints

• 0 <= The number of nodes in both trees <= 100.
• -100 <= Node.val <= 100

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Solution

DFS (preorder), where we check if payload is the same, then check left and right subtrees.

/**
 * 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) {}
 * };
 */
 
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // Trees are equal if left and right subtrees equal and current node
        std::function<bool(TreeNode*, TreeNode*)> runner;
        runner = [&](TreeNode *lhs, TreeNode *rhs) -> bool {
            // base case, both nullptr
            if (!lhs && !rhs) {
                return true;
            }
            // One nullptr while other is not
            if ((!lhs && rhs) || (lhs && !rhs)) {
                return false;
            }
            // lhs && rhs contain payloads, compare
            if (lhs->val != rhs->val) {
                return false;
            }
            // result is if both subtrees equal
            return runner(lhs->left, rhs->left) && runner(lhs->right, rhs->right);
        };
        return runner(p, q);
    }
};