Same Tree Up to Swaps

Medium

You are given the roots of two binary trees, first and second. In the first tree you may pick any node and swap its left and right subtrees, and you may do this for any number of nodes. Return True if such swaps can turn the first tree into the second (same shape, same values in matching nodes), and False otherwise.

Example 1

first=tree_node([4, 7, 2, None, 5]), second=tree_node([4, 2, 7, None, None, 5]) → True

Swap the children of the root 4: 2 goes left and 7 goes right. Node 7 had 5 as its right child; swap 7's children too and 5 becomes the left one. The trees now match.

Example 2

first=tree_node([1, 2, 3]), second=tree_node([1, 2, 4]) → False

The second tree has a 4 and the first one does not; no swaps can fix that.

Example 3

first=tree_node([]), second=tree_node([8]) → False

An empty tree never matches a one-node tree.

Constraints

0 ≤ number of nodes in each tree ≤ 100
0 ≤ Node.val ≤ 99
Within each tree the node values are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium All Leaf Paths With a Given Total Medium Tree Into a Right Chain Medium Digit Branch Totals Medium

Input

first=tree_node([4, 7, 2, None, 5]), second=tree_node([4, 2, 7, None, None, 5])

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.