LeetCode 971 - Flip Binary Tree To Match Preorder Traversal

This problem asks us to manipulate a binary tree so that its pre-order traversal matches a given sequence called voyage.

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 971

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to manipulate a binary tree so that its pre-order traversal matches a given sequence called voyage. In other words, we are given a tree and a list of integers, and we want to see if we can transform the tree by flipping nodes (swapping their left and right children) so that when we traverse the tree in pre-order (root → left → right), the sequence of node values exactly matches voyage.

The input consists of a binary tree with n nodes, where each node value is unique and ranges from 1 to n, and an array voyage of length n containing unique values from 1 to n. The output should be a list of node values that we flipped to achieve the matching traversal. If it is impossible to match voyage, the output should be [-1].

The problem constraints are relatively small (n <= 100), which suggests that a recursive or depth-first approach will be efficient enough. Each node value is unique, which guarantees that during traversal we can always identify if a subtree is correct or requires flipping.

Important edge cases to consider include:

  1. The tree is already in the correct pre-order, requiring no flips.
  2. A mismatch occurs at a node where flipping cannot fix the sequence.
  3. The tree has a single node or is skewed (all left or all right), which tests simple base cases.

Approaches

The brute-force approach would try every combination of flips at each node recursively, generating all possible pre-order traversals and comparing with voyage. While correct, this approach is computationally expensive because each node can either be flipped or not, resulting in O(2^n) combinations.

The optimal approach leverages DFS traversal and greedy flips. We traverse the tree in pre-order while keeping track of the position in voyage. At each node, if the left child exists but its value does not match the next value in voyage, we know we must flip the current node. This avoids unnecessary exploration of invalid paths and only flips when required. If a node's value does not match the expected value at any point, the traversal is impossible, and we return [-1].

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explore all flip combinations recursively and check pre-order
Optimal O(n) O(n) Single DFS pass with greedy flipping guided by voyage

Algorithm Walkthrough

  1. Initialize an index pointer i to track the current position in voyage.
  2. Initialize an empty list flipped to store nodes that we flip.
  3. Define a recursive DFS function that takes a node as input.
  4. If the node is None, return True because an empty subtree matches trivially.
  5. If the node's value does not match voyage[i], return False because it is impossible to match.
  6. Increment i because the current node matches the expected value.
  7. If the left child exists and its value does not match voyage[i] (the next expected value), flip the node: swap its left and right children and record its value in flipped.
  8. Recursively call DFS on the left child. If it returns False, return False.
  9. Recursively call DFS on the right child. If it returns False, return False.
  10. If all recursive calls succeed, return True.
  11. After DFS completes, if it returned True, return the flipped list. Otherwise, return [-1].

Why it works: The algorithm maintains an invariant that the portion of the tree already traversed matches the voyage up to index i. By only flipping when the next expected value does not match the left child, we minimize flips and guarantee correctness. Each node is visited once, ensuring linear time.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
        flipped = []
        i = 0

        def dfs(node: Optional[TreeNode]) -> bool:
            nonlocal i
            if not node:
                return True
            if node.val != voyage[i]:
                return False
            i += 1
            if node.left and i < len(voyage) and node.left.val != voyage[i]:
                flipped.append(node.val)
                node.left, node.right = node.right, node.left
            if dfs(node.left) and dfs(node.right):
                return True
            return False

        return flipped if dfs(root) else [-1]

Explanation: The dfs function recursively ensures the current subtree matches the voyage. We flip a node only if the left child's value does not match the next expected value. The index i keeps track of our position in voyage. The flipped list accumulates nodes that were flipped. If at any point the node value does not match voyage[i], we return [-1] indicating failure.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flipMatchVoyage(root *TreeNode, voyage []int) []int {
    flipped := []int{}
    i := 0

    var dfs func(node *TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        if node.Val != voyage[i] {
            return false
        }
        i++
        if node.Left != nil && i < len(voyage) && node.Left.Val != voyage[i] {
            flipped = append(flipped, node.Val)
            node.Left, node.Right = node.Right, node.Left
        }
        return dfs(node.Left) && dfs(node.Right)
    }

    if dfs(root) {
        return flipped
    }
    return []int{-1}
}

Go-specific notes: nil is used instead of None. Slice appends handle dynamically growing the flipped list. The dfs function is a closure capturing i and flipped.

Worked Examples

Example 1: root = [1,2], voyage = [2,1]

Start at root 1, expected voyage[0] = 2. Mismatch immediately → return [-1].

Example 2: root = [1,2,3], voyage = [1,3,2]

  • Root 1 matches voyage[0], increment i = 1.
  • Left child 2 ≠ voyage[1] = 3, flip 1. Record 1 in flipped.
  • Recurse left: now 3 matches voyage[1], increment i = 2.
  • Recurse left and right: None → return True.
  • Recurse right: 2 matches voyage[2], increment i = 3. Done. Return [1].

Example 3: root = [1,2,3], voyage = [1,2,3]

  • Root 1 matches voyage[0], increment i = 1.
  • Left child 2 matches voyage[1], increment i = 2.
  • Right child 3 matches voyage[2], increment i = 3. No flips needed → return [].

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once during DFS
Space O(n) Recursion stack in worst case skewed tree, plus flipped list

The algorithm is efficient because it only traverses each node once and performs constant-time operations at each node.

Test Cases

# Provided examples
assert Solution().flipMatchVoyage(TreeNode(1, TreeNode(2)), [2,1]) == [-1]  # impossible
assert Solution().flipMatchVoyage(TreeNode(1, TreeNode(2), TreeNode(3)), [1,3,2]) == [1]  # flip root
assert Solution().flipMatchVoyage(TreeNode(1, TreeNode(2), TreeNode(3)), [1,2,3]) == []  # no flip needed

# Edge cases
assert Solution().flipMatchVoyage(TreeNode(1), [1]) == []  # single node, no flip
assert Solution().flipMatchVoyage(None, []) == []  # empty tree
assert Solution().flipMatchVoyage(TreeNode(1, TreeNode(2, TreeNode(3))), [1,3,2]) == [1,2]  # multiple flips in skewed tree
Test Why
[1,2], voyage [2,1] Tests impossible scenario
[1,2,3], voyage [1,3,2] Tests single flip at root