dsa · easy

Symmetric Tree

A binary tree is **symmetric** when its left and right sides are mirror images of each other: folding the tree down the root lines every node up with a partner of the same value.

Arguments

• root — binary tree as nested [val, left, right] or None

Each node is [val, left, right] or None. Return whether root is symmetric. An empty tree is symmetric.

Example

root = [1, [2, [3, None, None], [4, None, None]], [2, [4, None, None], [3, None, None]]].

The left child of the root is 2 with children 3, 4. The right child is 2 with children 4, 3. Those two subtrees are mirrors, and the values match, so the answer is true.

[1, [2, None, [3, None, None]], [2, None, [3, None, None]]] is false: both inner 3s sit on the right, so the picture is not a mirror.

Constraints

Number of nodes in [0, 1000] -100 <= val <= 100 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[1, [2, [3, None, None], [4, None, None]], [2, [4, None, None], [3, None, None]]]

Expected:
true

Example 2

Input:
[1, [2, None, [3, None, None]], [2, None, [3, None, None]]]

Expected:
false

Open in the Dojo editor