easy

Symmetric Tree

Check whether a tree folds onto itself by comparing mirror pairs from the two halves.

1. Define the problem

Symmetric Tree

Given a binary tree, return true when it is a mirror of itself : fold the tree down the middle and the left half lands exactly on the right half. The tree arrives as a level-order array such as [1, 2, 2, 3, 4, 4, 3], with null for a missing child. Your function builds the tree and returns true or false. Compare the two halves as mirror pairs . Pair the left half’s left child with the right half’s right child, and the left half’s right child with the right half’s left child. The outside of one side must match the outside of the other.

Constraints

  • The number of nodes is between 0 and 1000
  • -100 ≤ node value ≤ 100
  • Input is a level-order array with null for a missing child
  • An empty tree counts as symmetric

Example

Inputvalues = [1, 2, 2, 3, 4, 4, 3]
Outputtrue

Explanation The root is 1. Its two children both hold 2. Under them, the far-left 3 pairs with the far-right 3, and the two middle 4s pair with each other. Every mirror pair agrees, so the tree is symmetric.

2. Know the words first

In plain terms

Mirror pair
Two positions that land on top of each other when you fold the tree down the middle. The root pairs with itself; after that, a node on the far left pairs with the node on the far right at the same depth.
Subtree
Any node together with everything hanging below it. A tree is symmetric when its left subtree is the mirror of its right subtree.
Depth
How many steps down from the root a node sits. The root is at depth 0.
3. Visualize the solution

One cell per mirror pair, in the order the pairs are checked

One cell per mirror pair, in the order the pairs are checked
Statusinit

Four mirror pairs will be checked, none of them yet.

What happens in this step

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

Left half:  2 with children 3 and 4
Right half: 2 with children 4 and 3

Each cell below is one pair waiting to be compared.
Step 1 of 6

Steps to visualize

  1. A mirror pair is two positions that meet when the tree is folded down the middle.
  2. Each cell fills in with the two values found in that pair once it has been checked.
  3. Pair 0 is the root against itself, and it always agrees.
  4. If any pair disagrees, or one side has a node where the other has nothing, the answer is false.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per mirror pair, in the order the pairs are checked
Statusinit

Four mirror pairs will be checked, none of them yet.

What happens in this step

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

Left half:  2 with children 3 and 4
Right half: 2 with children 4 and 3

Each cell below is one pair waiting to be compared.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function isSymmetric(values) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  function mirror(a, b) {
    if (a === null && b === null) {
      return true;
    }

    if (a === null || b === null) {
      return false;
    }

    if (a.val !== b.val) {
      return false;
    }

    return mirror(a.left, b.right) && mirror(a.right, b.left);
  }

  const root = buildTree(values);

  if (root === null) {
    return true;
  }

  return mirror(root.left, root.right);
}
Time
O(n)
Space
O(h)
6. Test cases

Test cases

InputExpectedCovers
values = [1, 2, 2, 3, 4, 4, 3]trueexample from the docstring
values = [1, 2, 2, null, 3, null, 3]falseboth 3s hang on the right, so the halves do not mirror
values = []truean empty tree is symmetric
values = [1]truea single node is symmetric
values = [1, 2, 3]falsethe two children hold different numbers
values = [2, 3, 3, 4, 5, 5, 4]truea second symmetric tree with repeated values

Keep reading