1+ /*
2+ * Problem: 101
3+ * Name: Symmetric Tree
4+ * Difficulty: Easy
5+ * Topic: Binary Trees
6+ * Link: https://leetcode.com/problems/symmetric-tree/
7+ */
8+
9+ #include < bits/stdc++.h>
10+ using namespace std ;
11+
12+ // Tree Node Implementation
13+ struct TreeNode {
14+ int val;
15+ TreeNode *left;
16+ TreeNode *right;
17+ TreeNode () : val(0 ), left(nullptr ), right(nullptr ) {}
18+ TreeNode (int x) : val(x), left(nullptr ), right(nullptr ) {}
19+ TreeNode (int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
20+ };
21+
22+ // Recursive Solution
23+ // Time Complexity: O(n)
24+ // Space Complexity: O(1)
25+ bool isSymmetricHelper (TreeNode *left, TreeNode* right);
26+ bool isSymmetricRecursive (TreeNode* root) {
27+ if (root == nullptr ) { return true ;}
28+ return isSymmetricHelper (root->left , root->right );
29+ }
30+ bool isSymmetricHelper (TreeNode *left, TreeNode* right){
31+ if (left == right) { return true ;}
32+ if (left == nullptr || right == nullptr ) { return false ;}
33+ return left->val == right->val &&
34+ isSymmetricHelper (left->left , right->right ) &&
35+ isSymmetricHelper (left->right , right->left );
36+ }
37+
38+ // Iterative Solution (BFS)
39+ // Time Complexity: O(n)
40+ // Space Complexity: O(n)
41+ bool isSymmetricBFS (TreeNode* root) {
42+ if (root == nullptr ) { return true ;}
43+ queue<TreeNode *> q;
44+ q.push (root->left );
45+ q.push (root->right );
46+ while (!q.empty ()){
47+ TreeNode *l = q.front (); q.pop ();
48+ TreeNode *r = q.front (); q.pop ();
49+ if (l == r) { continue ;}
50+ else if (l == nullptr || r == nullptr ) { return false ;}
51+ else if (l->val != r->val ) { return false ;}
52+ else {
53+ q.push (l->left );
54+ q.push (r->right );
55+ q.push (l->right );
56+ q.push (r->left );
57+ }
58+ }
59+ return true ;
60+ }
61+
62+ // Iterative Solution (DFS)
63+ // Time Complexity: O(n)
64+ // Space Complexity: O(n)
65+ bool isSymmetricDFS (TreeNode* root) {
66+ if (root == nullptr ) { return true ;}
67+ stack<TreeNode *> s;
68+ s.push (root->left );
69+ s.push (root->right );
70+ while (!s.empty ()){
71+ TreeNode *l = s.top (); s.pop ();
72+ TreeNode *r = s.top (); s.pop ();
73+ if (l == r) { continue ;}
74+ else if (l == nullptr || r == nullptr ) { return false ;}
75+ else if (l->val != r->val ) { return false ;}
76+ else {
77+ s.push (l->left );
78+ s.push (r->right );
79+ s.push (l->right );
80+ s.push (r->left );
81+ }
82+ }
83+ return true ;
84+ }
0 commit comments