parikshan

symmetric-tree

Difficulty: Easy  ·  Topic: Trees  ·  Practice it on parikshan: /practice/symmetric-tree/start

The story

A computer-vision team at an autonomous-driving company validates the structure of detected road markings. A symmetrical sign (a stop sign, a yield triangle, certain warning markers) should look the same on both sides of its central axis. The detection pipeline produces a tree of contour segments per sign. Before a sign is logged as a high-confidence match for "stop sign", the team checks whether the contour tree mirrors itself; if it does, that is strong evidence the sign is intact, not occluded, and not graffitied. The check has to run on every detected sign across every frame of every camera.

That is symmetric-tree. Once you see this problem in this framing, you will recognise it in palindrome-on-tree questions, layout-symmetry checks for UI testing, and chemistry tools that test molecular symmetry against a mirror plane.

What's actually being asked

Given a binary tree, decide whether it is a mirror image of itself: the left subtree of the root should be the mirror of the right subtree of the root, recursively. The empty tree is symmetric.

The naive approach

Build the mirror image of the tree (the invert-binary-tree operation) and compare it to the original with same-tree. That works and is O(n) time, but it allocates a whole second tree. Wasteful.

A subtler naive trap: traverse in-order and check that the resulting sequence reads as a palindrome. That works for values but not for structure. The tree [1, 2, 2, null, 3, 3, null] has a palindromic in-order sequence (2, 3, 1, 3, 2) but is structurally asymmetric. Sequences do not determine trees.

The key insight

Symmetry is a relationship between two subtrees of the same tree, not a property of a single subtree. Define a helper mirror(a, b) that compares two subtree roots and asks "is a the mirror of b?". Then the whole problem reduces to mirror(root.left, root.right).

The mirror recurrence is almost same-tree, with one twist: instead of comparing (a.left, b.left) and (a.right, b.right), you compare (a.left, b.right) and (a.right, b.left). The crossed pairing is the entire meaning of "mirror". Get the crossing right and the rest is bookkeeping.

This is the simplest tree problem that requires reasoning about two positions in the same tree simultaneously, exactly the "lockstep walk on two pointers" pattern from same-tree with the children swapped on one side.

Step-by-step approach

  1. Parse the level-order array into a tree.
  2. If the tree is empty, print true and exit.
  3. Define mirror(a, b):
    • If a is None and b is None, return true.
    • If exactly one is None, return false.
    • If a.val != b.val, return false.
    • Return mirror(a.left, b.right) AND mirror(a.right, b.left).
  4. Print mirror(root.left, root.right).

For 10⁴-node skewed inputs, use an iterative stack of (a, b) pairs, starting with (root.left, root.right). On each pop apply the base cases; on a real-real match push (a.left, b.right) and (a.right, b.left).

Worked example

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

       1
      / \
     2   2
    / \ / \
   3  4 4  3

mirror(root.left = 2, root.right = 2):
  values match
  mirror(left.left = 3, right.right = 3):
    values match, both subtrees empty -> true
  mirror(left.right = 4, right.left = 4):
    values match, both subtrees empty -> true
  -> true

Answer: true.

Asymmetric example:

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

       1
      / \
     2   2
      \   \
       3   3

mirror(root.left = 2, root.right = 2):
  values match
  mirror(left.left = None, right.right = 3):
    exactly one None -> false

Answer: false. The walk stops at the first mismatch.

Complexity

  • Time: O(n). Every node is visited at most once.
  • Space: O(h) for the stack.

You cannot do better in the worst case; a symmetric tree requires visiting every node to confirm it.

Common pitfalls

  • Not crossing the children: writing mirror(a.left, b.left) instead of mirror(a.left, b.right) turns the problem into same-tree. The crossed pairing is the algorithm.
  • Checking only values, not structure: [1, 2, 2, null, 3, 3, null] has equal values left-and-right but asymmetric null placement. You must compare None-ness, not just values.
  • Forgetting the empty-tree base case: [] is symmetric by convention; if you proceed to access root.left you crash. Guard at the top.
  • Confusing with same-tree: the input is one tree, not two. The two pointers walk into different sides of the same tree.

Where this shows up in the enterprise

  • Chemistry and drug discovery: RDKit and similar tools check for molecular symmetry against a mirror plane by comparing the bond-graph tree under a candidate axis. Symmetric molecules are achiral, which affects drug binding.
  • UI testing: Playwright and Cypress sometimes assert visual symmetry of layouts (a checkout form with left and right columns); the underlying DOM check is exactly this problem.
  • Computer vision: OpenCV's contour analysis and TensorFlow Object Detection use tree-of-contours symmetry checks for sign and face validation.
  • TypeScript compiler: the compiler checks structural type symmetry for some heuristic optimisations (mirrored union arms).
  • Game engines: Unity and Unreal validate that mirrored bone trees in rigged characters are consistent, so animations work in both left-handed and right-handed coordinate systems.
  • CDN configuration: Cloudflare and Fastly sometimes mirror a routing tree across two regions; configuration tools verify the mirror is structurally consistent before promoting.
  • Reddit and Hacker News: a/b test the layout of reply trees with mirror-image arrangements; symmetry validation ensures the same content renders consistently.

The pattern shows up wherever a structure has an intended mirror axis and that mirror has to be verified.

Variants you'll see elsewhere

  • valid-palindrome-list: same idea on a linked list, two pointers from both ends.
  • flip-equivalent-binary-trees: are two trees equal up to swapping children at some nodes?
  • merge-symmetric-pair: combine the mirrored halves into a representative subtree.
  • Tree-folding problems: any "fold the tree along the centre axis" operation requires a symmetry walk underneath.
  • Palindrome on tree paths: a different problem (one path, palindrome) but the same parallel-walk skeleton.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests and per-session dynamic private tests. The dynamic suite includes shapes that look symmetric on the value sequence but are not symmetric on structure; the only way to clear them is the crossed-pair walk.
  2. Hints are graduated. The first hint identifies that two pointers are needed. The third gives the crossed-pair skeleton. Each hint costs integrity.
  3. The AI training assistant offers Explain, Review, Find Bugs, Add Comments, Optimise in exam mode for a small integrity cost; free-form chat in practice mode.
  4. The dispute flow runs after the verdict. The common mistake on this problem is to write same-tree(left, right) instead of mirror(left, right); the dispute reviewer will gently point at the crossed pair.

Read the concept, attempt in practice mode, take hints when stuck, then redo in exam mode. When you can write the mirror recurrence in under three minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write is_symmetric by hand. An agent will. Your job is to:

  1. Recognise that "is this tree symmetric" requires comparing two halves of the same tree, not two trees, and that the cross is the heart of the algorithm.
  2. Tell the agent precisely: "lockstep walk with crossed pairs (a.left, b.right) and (a.right, b.left), base cases handle empty subtrees".
  3. Read the agent's code and verify the crossing. If you see (a.left, b.left) and (a.right, b.right), send it back; that is same-tree.
  4. Stress-test on the edge cases the agent will silently miss: the empty tree, a single node (trivially symmetric), [1, 2] (asymmetric), and any tree where values match symmetrically but null placement does not.

Candidates who can name "this is symmetric, crossed-pair walk" within five seconds are the ones who direct AI agents productively. Candidates who cannot recognise the pattern end up approving generated code that runs same-tree against an inverted copy and consumes twice the memory. parikshan is built to train the first kind.