Algorithm Puzzles: Symmetric Tree

Posted on Edited on In Views: Word count in article: 120 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Symmetric Tree

Puzzle

Puzzle from leetcode:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public:
    bool isSymmetric(const TreeNode* const root) {
        if (root != nullptr) {
            return isSubTreeSymmetric(root->left, root->right);
        }

        return true;
    }

  private:
    bool isSubTreeSymmetric(const TreeNode* const r, const TreeNode* const l) {
        if (r == l) {
            return true;
        }

        if (r == nullptr || l == nullptr) {
            return false;
        }

        return (r->val == l->val) && isSubTreeSymmetric(r->right, l->left) &&
               isSubTreeSymmetric(r->left, l->right);
    }
};