Symmetric Tree

+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) faces 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.

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

Every node has a partner at the mirrored spot across the root, and the partner of a left child is a right child. Walk the two halves in opposite directions at once, compare shape and value at each pair, and stop at the first pair that disagrees.

Compare each level with its reverse

Intuition

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 second example the bottom level reads -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 that level would read 3 3 and pass. Children of empty spots are empty too, so only real nodes add entries. Each node is visited once, O(n) time, and one level is 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, left to right, write down both child spots: the child's value if it is real, -1 if not. Collect the real children for the next level.
If that row differs from its reverse, return false.
Repeat on the next level 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

Compare the root's left subtree, at index 1, with its right subtree, 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). That is the definition of a mirror image applied one level down, so if every pair matches, the whole tree does.

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).

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 only remembers the pairs still waiting to be checked, so keep them on a stack of your own. The order of checking 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. The third example stops at its first bad pair, (3, 6), which holds 5 and 9.

Each real node is in at most one pair, so the time is O(n). The stack holds about one pending pair per level of the current path, O(h) space.

Algorithm

Push the pair (1, 2) on a stack.
Pop a pair (a, b) and test it as mirrors does: skip it if both spots are empty, return false if only one is or the values differ.
Otherwise 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

Checking each subtree on its own. In [1, 2, 2, 3, 4, 4, 3] the left subtree 2, 3, 4 is not symmetric, yet the whole tree is: it has to mirror the right subtree.
Pairing the children the wrong way. The pairs are (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.
Reading past the end. An index past the end is an empty spot; a single-node tree has no index 1 or 2 at all.
In Lua and R arrays start at 1: keep node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions3

What is the time complexity of Symmetric Tree?

Each real node is compared once, in one mirrored pair, so the time is O(n). The extra space is O(h) for the recursive and stack versions, and O(w), the widest level, for the level by level version.

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 the mirror image of its right subtree, so the comparison crosses over. The same pair check solves both, with the child pairs swapped.

Is a tree with a single node symmetric?

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

def isSymmetric(tree):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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 questions3

Similar problems