algoadvance

Leetcode 101. Symmetric Tree

Problem Statement

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

Example:

Input: 
    1
   / \
  2   2
 / \ / \
3  4 4  3

Output: true

Input:
    1
   / \
  2   2
   \   \
   3    3

Output: false

Clarifying Questions

  1. Is the tree always a binary tree?
    • Yes, the tree is always a binary tree.
  2. Can the tree have null nodes?
    • Yes, the tree can have null nodes, and these should be considered in the symmetry check.
  3. What should be the output for an empty tree?
    • An empty tree is symmetric, so the output should be true.

Strategy

To determine if the tree is symmetric, we need to check whether the left and right subtrees are mirror images of each other. We will implement a recursive function isMirror for this purpose. The main function will call this helper function with the left and right children of the root node.

Steps:

  1. If both nodes are null, they are symmetric.
  2. If one of them is null, they are not symmetric.
  3. If the values of the nodes are different, they are not symmetric.
  4. Recursively check the left subtree of the left node and the right subtree of the right node, as well as the right subtree of the left node and the left subtree of the right node.

Code

#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isMirror(TreeNode* left, TreeNode* right) {
    // Base case: both nodes are null
    if (left == NULL && right == NULL) {
        return true;
    }
    // One of them is null
    if (left == NULL || right == NULL) {
        return false;
    }
    // Check if the current nodes are identical and their subtrees are mirror images
    return (left->val == right->val) && 
           isMirror(left->left, right->right) &&
           isMirror(left->right, right->left);
}

bool isSymmetric(TreeNode* root) {
    if (root == NULL) {
        return true; // An empty tree is symmetric
    }
    // Check the left and right subtrees
    return isMirror(root->left, root->right);
}

// Helper function to test the code
int main() {
    // Create an example tree: [1, 2, 2, 3, 4, 4, 3]
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(3);
    
    // Test the function
    std::cout << (isSymmetric(root) ? "true" : "false") << std::endl; // Output: true

    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI