Flip Equivalent Binary Trees

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A **flip** on a binary tree picks a node and swaps its left and right child subtrees. Two binary trees are **flip equivalent** if some sequence of flips (possibly none) turns the first tree into the second. Given the roots root1 and root2, return true if they are flip equivalent and false otherwise. Within each tree all values are distinct. Two empty trees are flip equivalent.

Examples

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Flipping nodes 1, 3 and 5 turns the first tree into the second.
Input: root1 = [], root2 = []
Output: true
Both trees are empty.
Input: root1 = [], root2 = [1]
Output: false
One tree has a node and the other has none.

Constraints

  • 0 <= number of nodes in each tree <= 100
  • 0 <= Node.val <= 199
  • Values within each tree are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems