We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Flip Binary Tree To Match Preorder Traversal

Difficulty: Medium

Problem Description

You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the desired pre-order traversal of the binary tree. Any node in the binary tree can be flipped by swapping its left and right subtrees. Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage. Return a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match voyage, return the list [-1].

Key Insights

  • The problem requires matching the pre-order traversal of a binary tree with a given sequence by flipping nodes.
  • Flipping a node swaps its left and right children, which can affect the traversal order.
  • A depth-first search (DFS) approach can be used to traverse the tree and decide when to flip nodes based on the desired traversal sequence.
  • We maintain a list to track the values of flipped nodes and check for mismatches against the voyage.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree, since we may visit each node once. Space Complexity: O(n), for the recursion stack in the DFS traversal and the list of flipped nodes.

Solution

To solve this problem, we employ a depth-first search (DFS) approach to traverse the binary tree. We compare the values of the nodes encountered during the traversal with the values in the voyage array. If the current node's value does not match the corresponding value in the voyage, we check if flipping is necessary, which involves swapping the left and right children. We keep track of any nodes that are flipped in a list. If we reach a point where the traversal cannot match the voyage array, we return [-1].

Code Solutions

def flipMatchVoyage(root, voyage):
    def dfs(node, index):
        if not node:
            return True
        if index >= len(voyage) or node.val != voyage[index]:
            return False
        
        left_match = dfs(node.left, index + 1)
        if left_match:
            return True
        
        # If left does not match, we need to flip
        if node.right and node.right.val == voyage[index + 1]:
            flipped.append(node.val)  # Flip this node
            return dfs(node.right, index + 1) and dfs(node.left, index + 2)
        
        return False

    flipped = []
    if not dfs(root, 0):
        return [-1]
    return flipped
← Back to All Questions