Problem statement

Given the root of a binary tree, decide whether it is foldable: whether its left and right subtrees are mirror images of each other in structure, so that folding the tree along the vertical line through the root lays every node of one side exactly onto a node of the other.

Only the shape matters; node values are ignored. An empty tree is foldable. Return true or false.

Example 1

Input: root = [10,7,15,null,9,11]
Output: true
Explanation: 7's right child 9 faces 15's left child 11: the two sides are mirror images in shape (values do not matter).

Example 2

Input: root = [10,7,15,5,null,11]
Output: false
Explanation: 7 has a left child and 15 has a left child too — folded, 5 would land where 15 has no right child.

Example 3

Input: root = [1]
Output: true
Explanation: A single node folds onto itself.

Constraints

• 0 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^5

Hints for Foldable Binary Tree

1. Hint 1

   Folding pairs a node on the left with the node in the mirrored position on the right.

2. Hint 2

   Two subtrees are structural mirrors when both are empty, or both are non-empty and the first's left mirrors the second's right and the first's right mirrors the second's left.

3. Hint 3

   Apply that test to root.left and root.right — exactly the Symmetric Tree check, minus the value comparison.

How to solve Foldable Binary Tree

The tree is foldable exactly when the root's two subtrees are structural mirror images, which a simultaneous recursion over the pair checks node by node.

Approach

1. If the tree is empty, return true.
2. Define mirror(a, b): if either is empty, return whether both are; otherwise return mirror(a.left, b.right) && mirror(a.right, b.left).
3. Return mirror(root.left, root.right).

Why it works

Folding maps a node's left child onto its mirror partner's right child and vice versa. mirror checks precisely that every pair of mirrored positions is either filled on both sides or empty on both, recursively down to the leaves, so it returns true exactly when the fold matches every node.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• Comparing the left subtree with the right subtree directly (left with left) tests equality, not mirroring.
• Values are irrelevant here — unlike Symmetric Tree, do not compare them.

Reference solution

Python

from typing import Optional

def isFoldable(root: Optional[TreeNode]) -> bool:
    return root is None or _mirror(root.left, root.right)

def _mirror(a, b):
    if a is None or b is None:
        return a is None and b is None
    return _mirror(a.left, b.right) and _mirror(a.right, b.left)

Java

public static boolean isFoldable(TreeNode root) {
    return root == null || mirrorShape(root.left, root.right);
}

static boolean mirrorShape(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == null && b == null;
    return mirrorShape(a.left, b.right) && mirrorShape(a.right, b.left);
}

C++

static bool mirrorShape(TreeNode* a, TreeNode* b);

bool isFoldable(TreeNode* root) {
    return !root || mirrorShape(root->left, root->right);
}

static bool mirrorShape(TreeNode* a, TreeNode* b) {
    if (!a || !b) return !a && !b;
    return mirrorShape(a->left, b->right) && mirrorShape(a->right, b->left);
}

JavaScript

var isFoldable = function(root) {
    return root === null || mirrorShape(root.left, root.right);
};

function mirrorShape(a, b) {
    if (a === null || b === null) return a === null && b === null;
    return mirrorShape(a.left, b.right) && mirrorShape(a.right, b.left);
}

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium
• Sum of Nodes on the Longest Path from Root to Leaf Medium