Home
How to Check Symmetric Tree in C++ (Iterative and Recursion)?
Tags:, , , , , , , , , ,

How to Check Symmetric Tree in C++ (Iterative and Recursion)?

April 9, 2016 No Comments algorithms, BFS, c / c++, DFS, Recursion

Given a binary tree, you are asked to check whether it is a mirror of itself (i.e, symmetric around its center): https://leetcode.com/problems/symmetric-tree/

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Recursion

Recursion is your best friend in solving tree/graph-related problems e.g. because the tree/graph itself can be defined recursively. We need to provide a helper function to check if two sub-trees are symmetric. We need to compare the value of left nodes and right nodes, also recursively comparing their sub trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* left, TreeNode *right) {
        if ((left == NULL) && (right == NULL)) {
            return true;
        }
        if ((left != NULL) && (right != NULL)) {
            return (left->val == right->val) && 
                        isSymmetric(left->right, right->left) && 
                        isSymmetric(left->left, right->right);
        }
        return false;
    }
 
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        return isSymmetric(root->left, root->right);
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* left, TreeNode *right) {
        if ((left == NULL) && (right == NULL)) {
            return true;
        }
        if ((left != NULL) && (right != NULL)) {
            return (left->val == right->val) && 
                        isSymmetric(left->right, right->left) && 
                        isSymmetric(left->left, right->right);
        }
        return false;
    }

    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        return isSymmetric(root->left, root->right);
    }
};

Iterative

If you don’t like recursion because it may overflow your stack, you should go for iterative approaches by using stack or queue data structures depending how you implement the search, DFS (Depth First Search) or BFS (Breadth First Search) respectively. Please note that recursion often (most of the cases) implements the idea of DFS.

Using BFS, the implementation seems easier than Iterative DFS since we just need to have a Queue for storing the TreeNode pair (left and right). Start by putting the root node in the queue. At each iteration, we check if the queue is empty. If not, get the front node from the queue and push its children (two node pairs, indicating two subtrees) to the queue. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        queue<pair<TreeNode*, TreeNode*>> q;
        q.push(make_pair(root->left, root->right)); // push the root
        while (!q.empty()) {
            // get the front element from the queue
            pair<TreeNode*, TreeNode*> p = q.front();
            q.pop();
            if (!(p.first) && !(p.second)) {
                continue;
            }
            if ((!p.first) || !(p.second)) {
                return false;
            }
            // value not equal, then it is not symmetric
            if (p.first->val != p.second->val) {
                return false;
            }
            // push the sub trees for comparision
            q.push(make_pair(p.first->left, p.second->right));
            q.push(make_pair(p.first->right, p.second->left));
        }
        return true;
    }
};
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        queue<pair<TreeNode*, TreeNode*>> q;
        q.push(make_pair(root->left, root->right)); // push the root
        while (!q.empty()) {
            // get the front element from the queue
            pair<TreeNode*, TreeNode*> p = q.front();
            q.pop();
            if (!(p.first) && !(p.second)) {
                continue;
            }
            if ((!p.first) || !(p.second)) {
                return false;
            }
            // value not equal, then it is not symmetric
            if (p.first->val != p.second->val) {
                return false;
            }
            // push the sub trees for comparision
            q.push(make_pair(p.first->left, p.second->right));
            q.push(make_pair(p.first->right, p.second->left));
        }
        return true;
    }
};
symmetric_tree How to Check Symmetric Tree in C++ (Iterative and Recursion)? algorithms BFS c / c++ DFS Recursion

symmetric tree

What are the runtime complexity for both cases, if the number of nodes of the Tree is N? It is O(logN) on average for a balance tree. Could you write a Iterative approach using DFS (converted from recursion)?

Algorithms to Check if a Binary Tree is Symmetric

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
757 words
Last Post: Valid Anagram String Check Algorithms using Hash Table
Next Post: Depth First Search and Breadth First Search Algorithm to Sum Root to Leave Numbers in Binary Tree

The Permanent URL is: How to Check Symmetric Tree in C++ (Iterative and Recursion)?

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  3. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  4. Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree (BST),...
  5. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  6. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  7. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...
  8. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...

Leave a Reply