Problem

A tree is symmetric if its data and shape remain unchanged when it is reflected about the root node. Given a n-ary OR k-ary tree, determine whether it is symmetric.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input: 
        4
      / | \
    3   5   3
  /           \
9              9

Output: 
true

Explanation: 
The tree is symmetric when reflected about the root node. The left subtree [3, 9] mirrors the right subtree [3, 9].

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Output: 
false

Explanation: 
The tree is not symmetric because the left subtree has node 4 as left child of 2, but the right subtree has node 5 as left child of 2 (should be right child to be symmetric).

Example 3

1
2
3
4
5
6
7
8

Input: 
    1

Output: 
true

Explanation: 
A single node tree is always symmetric.

Example 4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Output: 
true

Explanation: 
The tree is symmetric. Left subtree structure [3[1,2], 4[4]] mirrors right subtree [3[2,1], 4[4]] when reflected.

Solution

Method 1 - Recursive Mirror Comparison

Intuition

A k-ary tree is symmetric if the left and right subtrees are mirror images of each other. For two subtrees to be mirrors, their root values must be equal, and the i-th child of the left subtree must be a mirror of the (n-1-i)-th child of the right subtree, where n is the number of children.

Approach

  1. Handle base cases: null tree or single node tree (both symmetric)
  2. For a tree to be symmetric, we need to check if left and right subtrees are mirrors
  3. Two subtrees are mirrors if:
    • Both roots have the same value
    • They have the same number of children
    • The i-th child of left subtree mirrors the (n-1-i)-th child of right subtree
  4. Use recursive helper function to compare mirrored subtrees
  5. Return true only if all corresponding mirrored nodes match

Code

 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
31

struct Node {
    int val;
    vector<Node*> children;
    Node(int x) : val(x) {}
};

class Solution {
public:
    bool isSymmetric(Node* root) {
        if (!root) return true;
        return isMirror(root, root);
    }
    
private:
    bool isMirror(Node* left, Node* right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        if (left->val != right->val) return false;
        
        int n = left->children.size();
        if (n != right->children.size()) return false;
        
        for (int i = 0; i < n; i++) {
            if (!isMirror(left->children[i], right->children[n - 1 - i])) {
                return false;
            }
        }
        
        return true;
    }
};
 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
31
32
33
34
35
36

type Node struct {
    Val      int
    Children []*Node
}

func isSymmetric(root *Node) bool {
    if root == nil {
        return true
    }
    return isMirror(root, root)
}

func isMirror(left, right *Node) bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil {
        return false
    }
    if left.Val != right.Val {
        return false
    }
    
    n := len(left.Children)
    if n != len(right.Children) {
        return false
    }
    
    for i := 0; i < n; i++ {
        if !isMirror(left.Children[i], right.Children[n-1-i]) {
            return false
        }
    }
    
    return true
}
 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
31
32

class Node {
    int val;
    List<Node> children;
    Node(int x) { 
        val = x; 
        children = new ArrayList<>();
    }
}

class Solution {
    public boolean isSymmetric(Node root) {
        if (root == null) return true;
        return isMirror(root, root);
    }
    
    private boolean isMirror(Node left, Node right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        
        int n = left.children.size();
        if (n != right.children.size()) return false;
        
        for (int i = 0; i < n; i++) {
            if (!isMirror(left.children.get(i), right.children.get(n - 1 - i))) {
                return false;
            }
        }
        
        return true;
    }
}
 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

class Node:
    def __init__(self, val: int = 0):
        self.val = val
        self.children = []

class Solution:
    def isSymmetric(self, root: Node) -> bool:
        if not root:
            return True
        return self._isMirror(root, root)
    
    def _isMirror(self, left: Node, right: Node) -> bool:
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        
        n = len(left.children)
        if n != len(right.children):
            return False
        
        for i in range(n):
            if not self._isMirror(left.children[i], right.children[n - 1 - i]):
                return False
        
        return True

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once
  • 🧺 Space complexity: O(h), where h is the height of the tree due to recursion stack space

Method 2 - Iterative Level-by-Level Comparison

Intuition

Instead of recursion, we can use an iterative approach with queues to compare nodes level by level. For each level, we check if the nodes are arranged symmetrically by comparing values from both ends moving inward.

Approach

  1. Use BFS to traverse the tree level by level
  2. For each level, collect all node values in a list
  3. Check if the level values form a symmetric pattern
  4. For null nodes, use a special marker to maintain position information
  5. Continue until all levels are processed
  6. Return true if all levels are symmetric

Code

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class Solution {
public:
    bool isSymmetric(Node* root) {
        if (!root) return true;
        
        queue<Node*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            vector<Node*> nextLevel;
            
            for (int i = 0; i < size; i++) {
                Node* node = q.front();
                q.pop();
                
                if (node) {
                    level.push_back(node->val);
                    for (Node* child : node->children) {
                        nextLevel.push_back(child);
                    }
                } else {
                    level.push_back(INT_MIN); // Marker for null
                }
            }
            
            if (!isLevelSymmetric(level)) return false;
            
            for (Node* node : nextLevel) {
                q.push(node);
            }
        }
        
        return true;
    }
    
private:
    bool isLevelSymmetric(const vector<int>& level) {
        int left = 0, right = level.size() - 1;
        while (left < right) {
            if (level[left] != level[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

func isSymmetricIterative(root *Node) bool {
    if root == nil {
        return true
    }
    
    queue := []*Node{root}
    
    for len(queue) > 0 {
        size := len(queue)
        var level []int
        var nextLevel []*Node
        
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            
            if node != nil {
                level = append(level, node.Val)
                for _, child := range node.Children {
                    nextLevel = append(nextLevel, child)
                }
            } else {
                level = append(level, -1001) // Marker for null
            }
        }
        
        if !isLevelSymmetric(level) {
            return false
        }
        
        queue = append(queue, nextLevel...)
    }
    
    return true
}

func isLevelSymmetric(level []int) bool {
    left, right := 0, len(level)-1
    for left < right {
        if level[left] != level[right] {
            return false
        }
        left++
        right--
    }
    return true
}
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public boolean isSymmetricIterative(Node root) {
        if (root == null) return true;
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            List<Node> nextLevel = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                
                if (node != null) {
                    level.add(node.val);
                    for (Node child : node.children) {
                        nextLevel.add(child);
                    }
                } else {
                    level.add(null);
                }
            }
            
            if (!isLevelSymmetric(level)) return false;
            
            for (Node node : nextLevel) {
                queue.offer(node);
            }
        }
        
        return true;
    }
    
    private boolean isLevelSymmetric(List<Integer> level) {
        int left = 0, right = level.size() - 1;
        while (left < right) {
            if (!Objects.equals(level.get(left), level.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
 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
31
32
33
34
35
36
37
38

from collections import deque

class Solution:
    def isSymmetricIterative(self, root: Node) -> bool:
        if not root:
            return True
        
        queue = deque([root])
        
        while queue:
            size = len(queue)
            level = []
            next_level = []
            
            for _ in range(size):
                node = queue.popleft()
                
                if node:
                    level.append(node.val)
                    next_level.extend(node.children)
                else:
                    level.append(None)
            
            if not self._is_level_symmetric(level):
                return False
            
            queue.extend(next_level)
        
        return True
    
    def _is_level_symmetric(self, level: List[int]) -> bool:
        left, right = 0, len(level) - 1
        while left < right:
            if level[left] != level[right]:
                return False
            left += 1
            right -= 1
        return True

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the tree. We visit each node once
  • 🧺 Space complexity: O(w), where w is the maximum width of the tree (space for queue and level storage)