Start learning free

LESSON 296 OF 338 · BINARY TREES

Symmetric Tree in Go: Recursive Mirror Check

Practice O(n) Read the full explanation

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

 

Follow up: Could you solve it both recursively and iteratively?
STEP 1 OF 7
    Ctrl + Enter to check

    GO · BINARY TREES

    Symmetric Tree in Go, explained

    Problem overview

    The function isSymmetric receives the root of a binary tree, a *TreeNode, and returns true when the tree is a mirror image of itself around its center line. The tree has between 1 and 1000 nodes, with values from -100 to 100.

    The tree [1,2,2,3,4,4,3] is symmetric: the root's two children are both 2, the left child's children are 3 and 4, and the right child's children are 4 and 3, which is the same pair in reverse. The tree [1,2,2,null,3,null,3] is not: both 2s have only a right child, so the left side has a 3 on the inside while the right side has a 3 on the outside, and the shapes don't mirror.

    Approach: compare two subtrees that should mirror each other

    Checking the left half against the right half takes a pair of nodes at a time. Two subtrees first and second mirror each other when:

    • both are empty, or both exist and hold the same value, and
    • first's left subtree mirrors second's right subtree (the outer pair), and
    • first's right subtree mirrors second's left subtree (the inner pair).

    That is a recursive definition with a clear base case. A whole tree is symmetric when it mirrors itself. Calling the helper with the same root for both arguments does this: one pointer walks the tree going left while the other walks the same tree going right, and they must always meet equal values. It does some work twice, since each pair is checked from both sides, but the code stays short.

    The statement also suggests an iterative version with a queue. This lesson uses recursion.

    Step by step

    1. Delegate. isSymmetric returns isMirror(root, root).
    2. Declare the helper isMirror(first, second *TreeNode) bool. Go lets two parameters of the same type share one type name. A function can be used above the line where it is declared, so the order in the file doesn't matter.
    3. Both empty: return true. Two empty subtrees are mirror images, and this is the base case at the leaves.
    4. Exactly one empty: return false. The previous check already returned for "both empty", so this condition means one node is missing and the other isn't. The order of these two checks matters.
    5. Different values: return false. Both pointers are non-nil here, so reading .Val is safe.
    6. Outer pair: if isMirror(first.Left, second.Right) is false, return false without checking the inner pair.
    7. Inner pair: return isMirror(first.Right, second.Left), which decides the answer when everything before it passed.

    The solution in Go

    func isSymmetric(root *TreeNode) bool {
	return isMirror(root, root)
}

func isMirror(first, second *TreeNode) bool {
	if first == nil && second == nil {
		return true
	}
	if first == nil || second == nil {
		return false
	}
	if first.Val != second.Val {
		return false
	}
	if !isMirror(first.Left, second.Right) {
		return false
	}
	return isMirror(first.Right, second.Left)
}

    The Go details worth a closer look:

    • Nil pointers. A missing child is a nil *TreeNode. Comparing a pointer with nil is safe; reading a field through a nil pointer panics. That is why both nil checks come before first.Val.
    • first, second *TreeNode. The type applies to both names. It is the same as writing first *TreeNode, second *TreeNode.
    • Pointer comparison. first == nil compares an address, not a value. Two different non-nil pointers are never equal, so the code compares .Val, not the pointers.
    • && and || short-circuit. Go stops evaluating as soon as the answer is known, though the checks here don't depend on that.
    • Early returns. There is no else after a return. The idiomatic Go style is a sequence of guard checks, each ending the function when it fails.

    Complexity

    Time: O(n). Each call compares one pair of nodes and makes at most two more calls. Because the same tree is compared with itself, each node is visited twice, once on each side, which is still linear. The calls stop at the first mismatch.

    Space: O(h) for the recursion, where h is the height of the tree: about log n for a balanced tree and n for a tree where each node has a single child.

    Edge cases and common mistakes

    • A single node. [1] is symmetric. Both pairs of children are empty.
    • Comparing the wrong children. Checking first.Left against second.Left tests whether two trees are identical, not mirrored. In the mirror check the outer children pair up, and so do the inner ones.
    • Equal values, different shapes. In [1,2,2,2,null,2] every value is paired with an equal one, yet both 2s have only a left child. The left 2's child is on the outer side and the right 2's child is on the inner side, so the shapes do not mirror. The one-empty check is what returns false here.
    • Checking only the values. Reading the values of each level is not enough, because the positions of the missing nodes count too.
    • Swapping the two nil checks. If "one is nil" came first, two empty subtrees would hit it and the function would return false for every leaf.

    Testing

    • [1,2,2,3,4,4,3] gives true.
    • [1,2,2,null,3,null,3] gives false.
    • [1] gives true.
    • [1,2,3] gives false.
    • [1,2,2,2,null,2] gives false.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free