Solution to Leetcode problem 971 Flip Binary Tree To Match Preorder Traversal

This is the third problem of the Leetcode contest 118. It is a problem on binary trees (My favorite kind of problem!). It is using the following 2 definitions:

• “A node in the binary tree can be flipped by swapping the left child and the right child of that node”
• Preorder traversal of a node: we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child

The question is: Given a binary tree T, with nodes with unique values, and a array A, is there a way to flip nodes of T such that a preorder traversal of T matches A's values in order?

Leetcode problem 971 statement

To solve the problem, we use a divide and conquer strategy with the simple observation that given a binary tree, it is possible to flip it so that a preorder traversal matches A if and only if:

• A[0] == root.value
• A = [a, A1, A2] such that you can flip T.left and the preorder traversal matchesA1 and you can flip T.right and the preorder traversal matchesA2
  OR
  A = [a, A1, A2] such that you can flip T.right and the preorder traversal matchesA1 and you can flip T.left and the preorder traversal matchesA2.

Where it gets interesting is that since the nodes have unique values, we don’t…