Pattern visualizer
Symmetric Tree
Symmetry is not a property you can check on one node at a time. It is an equality between two subtrees walked in opposite directions: the left subtree's LEFT child must match the right subtree's RIGHT child, and the left subtree's RIGHT child must match the right subtree's LEFT child. So the helper takes a pair of nodes, not one. Two missing nodes are a match, one missing node is a mismatch, and a value mismatch ends it. Otherwise recurse on the outer pair and the inner pair, and the answer is true only if both are. Animated on: Tree [1, 2, 2, 3, 4, 4, 3]. Is it a mirror of itself around its centre? Answer: true..
Two pointers walking a tree in opposite directions
Call stack
isSymmetric(1): a tree is symmetric when its LEFT subtree is the mirror image of its RIGHT subtree. The root is on the axis and needs no partner, so the whole question becomes isMirror(2, 2).
1FUNCTION isSymmetric(root)2 RETURN isMirror(root.left, root.right)3FUNCTION isMirror(a, b)4 IF a = null AND b = null: RETURN true5 IF a = null OR b = null OR a.val != b.val: RETURN false6 outer <- isMirror(a.left, b.right)7 inner <- isMirror(a.right, b.left)8 RETURN outer AND inner
← / → step · space play · Home restart