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; } };
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
- Teaching Kids Programming – Iterative Algorithm to Check if a Binary Tree is Symmetric
- Teaching Kids Programming – Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm
- Teaching Kids Programming – Recursive Algorithm to Determine if a Binary Tree is Symmetric
- How to Check Symmetric Tree in C++ (Iterative and Recursion)?
–EOF (The Ultimate Computing & Technology Blog) —
loading...
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