LeetCode Same Tree: DFS, 3 Lines of Code

Overview

DFS could solve this LeetCode Same Tree problem elegantly with only 3 lines of code, two trees are the same when the tree structure and the node value are same

LeetCode Same Tree Problem

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

DFS Solution and the Code

Standard DFS problem: see the following code:

bool isSameTree(TreeNode *p, TreeNode *q) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == p && NULL == q)
            return true;
        if(NULL != p && NULL != q)
            return     (p->val == q->val)
                    && isSameTree(p->left, q->left)
                    && isSameTree(p->right, q->right);
        return false;
    }

Tried this LeetCode Same Tree problem again and come up a bit different implementation:

bool isSameTree(TreeNode *p, TreeNode *q) {
    if (NULL == p) return NULL == q;
    if (NULL == q) return NULL == p;
    return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

Summary

DFS could solve this LeetCode Same Tree problem elegantly with only 3 lines of code, two trees are the same when the tree structure and the node value are same

Written on April 18, 2013