Symmetric Tree

Q: What is the time complexity of Symmetric Tree?

Each real node is compared once, as part of one mirrored pair, so the time is O(n) . The recursive and stack versions use O(h) extra space for the pending pairs along the current path. The level by level version keeps one level in memory, O(w) for the widest level.

Q: How do you check if a binary tree is symmetric without recursion?

Keep a stack or a queue of pairs of nodes that must mirror each other, starting with the root's two children. Take out a pair, fail on a mismatch, and add the outer pair and the inner pair of their children. If the stack runs empty without a mismatch, the tree is symmetric.

Q: What is the difference between a symmetric tree and two identical trees?

Two trees are identical when you compare left with left and right with right. A tree is symmetric when its left subtree is identical to the mirror image of its right subtree, so the comparison crosses over: left with right and right with left. The same pair-checking code solves both problems with the child pairs swapped.

Q: Is a tree with a single node symmetric?

Yes. A single node has two empty child spots, and two empty spots mirror each other. A root with exactly one child is never symmetric, because that child faces an empty spot.

EasyTree traversal

+10

You get a binary tree stored in the array tree in level order. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries. Return true if the tree is a mirror image of itself around a vertical line through the root, and false otherwise. The shape and the values must both match.

Function

isSymmetric(tree: integer-array) → boolean

treeinteger-array: the binary tree in level order, with -1 for an empty spot
Returnsboolean: true if the tree mirrors itself, false otherwise

Constraints

1 ≤ tree.length ≤ 32767
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 1000.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.

Examples

Input: tree = [1, 2, 2, 3, 4, 4, 3]
Output: true
Explanation: Fold the tree down the middle. The two 2s at indexes 1 and 2 meet, the outer 3s at indexes 3 and 6 meet, and the inner 4s at 4 and 5 meet.

Input: tree = [1, 2, 2, -1, 3, -1, 3]
Output: false
Explanation: Both 3s hang on the right of their parents. In a mirror image the right child of the left 2 (index 4) must face the left child of the right 2 (index 5), and index 5 is empty.

Input: tree = [4, 6, 6, 5, -1, -1, 9]
Output: false
Explanation: The shape is a mirror image: index 3 faces index 6 and both hold a node. Their values differ, 5 against 9, so the tree is not symmetric.

+16 hidden tests on Submit

Follow-up

If the shape mirrors itself but some values do not, what is the fewest node values you must change to make the tree symmetric?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Symmetry is a property of pairs. Every node has a partner at the mirrored spot on the other side of the root, and the partner of a left child is a right child. So you never compare a node with its own children: you walk the two halves of the tree in opposite directions at the same time, compare shape and value at each pair, and stop at the first pair that disagrees.

Compare each level with its reverse

Intuition

First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2. A child is real only if its index is inside the array and the value there is not -1. In [1, 2, 2, 3, 4, 4, 3], the root 1 has its children at indexes 1 and 2, and the 2 at index 1 has its children at 3 and 4.

Now look at the tree one level at a time. A mirror image reads the same from left to right as from right to left, so every level, written out with its empty spots, must read the same in both directions. In the first example the levels below the root read 2 2 and 3 4 4 3. In the second they read 2 2 and then -1 3 -1 3, which reversed is 3 -1 3 -1, so the answer is false.

The empty spots must stay in the row. Without them the second example's bottom level would read 3 3 and pass. Write one entry for each child spot of each real node on the level, -1 for an empty one; children of empty spots are empty too, so they add nothing. Each node is visited once, so the time is O(n), and one level is kept in memory at a time, O(w) for the widest level w.

Algorithm

Start with a list that holds the root index 0.
For each index in the list, from left to right, write down both child spots: the child's value if it is real, -1 if it is empty. Collect the real children for the next level.
If that row of child spots differs from its reverse, return false.
Move to the next level and repeat until it is empty, then return true.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Recursion on mirrored pairs

Intuition

Instead of whole levels, compare two subtrees: the root's left subtree, which starts at index 1, and its right subtree, which starts at index 2. Two spots mirror each other when both are empty, or when both hold the same value and their children cross over. The left child of one mirrors the right child of the other (the outer pair), and the right child of one mirrors the left child of the other (the inner pair).

In the first example, mirrors(1, 2) compares the two 2s, then calls mirrors(3, 6) for the outer 3s and mirrors(4, 5) for the inner 4s. Each of those finds only empty spots below and returns true. In the second example, mirrors(4, 5) finds a 3 at index 4 facing an empty spot at index 5, returns false, and the false climbs back to the top.

Every real node belongs to at most one pair, so the time is O(n). The call stack is as deep as the tree, O(h), which is at most 14 frames here.

Algorithm

Write mirrors(a, b). A spot is empty when its index is past the end or holds -1. If both spots are empty, return true; if only one is, return false.
If tree[a] and tree[b] differ, return false.
Otherwise return mirrors(2*a+1, 2*b+2) and mirrors(2*a+2, 2*b+1).
Return mirrors(1, 2). A root with no children gives two empty spots, which is true.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Explicit stack of mirrored pairs

Intuition

The recursion needs only one thing: the pairs still waiting to be checked. Keep those pairs on a stack of your own and the calls disappear. Start with the pair (1, 2). Pop a pair. If both spots are empty, there is nothing below them, so move on. If one is empty or the values differ, the tree is not symmetric. Otherwise push the outer pair (2*a+1, 2*b+2) and the inner pair (2*a+2, 2*b+1).

The order in which you check the pairs does not matter, because the tree is symmetric only if every pair matches. A stack gives depth-first order; a queue would give level order and work the same way. The third example stops at its first bad pair, (3, 6), which holds 5 and 9.

Each pop handles one pair and each real node is in at most one pair, so the time is O(n). The stack keeps about one pending pair per level of the current path, O(h) space, and there is no recursion limit to worry about.

Algorithm

Push the pair (1, 2) on a stack.
Pop a pair (a, b). If both spots are empty (index past the end or -1), go on to the next pair.
If only one spot is empty, or tree[a] differs from tree[b], return false.
Push (2*a+1, 2*b+2) and (2*a+2, 2*b+1).
When the stack is empty, return true.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Pitfalls and edge cases

Most wrong answers compare the wrong pair of nodes, or forget that an empty spot is part of the shape.

Checking each subtree on its own. The left subtree does not have to be symmetric by itself: in [1, 2, 2, 3, 4, 4, 3] the subtree 2, 3, 4 is not, and the whole tree is. It has to mirror the right subtree.
Pairing the children the wrong way. The left child of one side faces the right child of the other: (2*a+1, 2*b+2) and (2*a+2, 2*b+1), never (2*a+1, 2*b+1).
Comparing values only. Drop the empty spots from [1, 2, 2, -1, 3, -1, 3] and every level reads the same both ways, yet the tree is not symmetric. Keep -1 in a level row, or check emptiness in the pair test.
Reading past the end. An index past the end of the array is an empty spot. Check a < n before reading tree[a]; a single-node tree has no index 1 or 2 at all.
Stopping at the first matching pair. One good pair proves nothing; return true only after every pair has been checked.
Mixing up the offset in Lua and R, where arrays start at 1. Keep the node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions4

What is the time complexity of Symmetric Tree?

Each real node is compared once, as part of one mirrored pair, so the time is O(n). The recursive and stack versions use O(h) extra space for the pending pairs along the current path. The level by level version keeps one level in memory, O(w) for the widest level.

How do you check if a binary tree is symmetric without recursion?

Keep a stack or a queue of pairs of nodes that must mirror each other, starting with the root's two children. Take out a pair, fail on a mismatch, and add the outer pair and the inner pair of their children. If the stack runs empty without a mismatch, the tree is symmetric.

What is the difference between a symmetric tree and two identical trees?

Two trees are identical when you compare left with left and right with right. A tree is symmetric when its left subtree is identical to the mirror image of its right subtree, so the comparison crosses over: left with right and right with left. The same pair-checking code solves both problems with the child pairs swapped.

Is a tree with a single node symmetric?

Yes. A single node has two empty child spots, and two empty spots mirror each other. A root with exactly one child is never symmetric, because that child faces an empty spot.

Python

def isSymmetric(tree):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

tree = [1, 2, 2, 3, 4, 4, 3]

Expected

true

Symmetric Tree

Function

Constraints

Examples

Hints

Solution

Compare each level with its reverse

Recursion on mirrored pairs

Explicit stack of mirrored pairs

Pitfalls and edge cases

Frequently asked questions4

Similar problems