971. Flip Binary Tree To Match Preorder Traversal

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

In this problem, we are working with a binary tree where each node has a unique integer value assigned from 1 to n. The root of this binary tree is provided to us. Additionally, we are given a sequence of n values named voyage. This sequence represents the desired pre-order traversal of the binary tree.

Pre-order traversal is a method where we visit the root node first, then recursively do a pre-order traversal of the left subtree, followed by a pre-order traversal of the right subtree.

One key aspect of the problem is that we can flip any node in the binary tree. Flipping a node means swapping its left and right subtrees. Our objective is to flip the smallest number of nodes in the tree so that the actual pre-order traversal matches the given voyage sequence.

If it is possible to achieve a match, we need to return a list of the values of all flipped nodes. If it's not possible, we simply return [-1].

Intuition

To solve this problem, we will use a depth-first search (DFS) strategy that follows the pre-order traversal pattern. Since we're matching the voyage sequence in a pre-order fashion, we can keep track of where we are in the voyage sequence using a variable, let's say i.

We start with the root node and explore the tree in pre-order, checking at each step:

  1. If the current node is None, we just return as there's nothing to process.
  2. If the current node's value does not match the voyage sequence at index i, it means it's impossible to achieve the desired pre-order by flipping nodes. In this case, we set a flag (ok) to False.
  3. If the current node has a left child and its value does not match the next value in the voyage sequence, this means we need to flip the current node. We add the current node's value to the answer list and continue the traversal with the right subtree first, followed by the left subtree.
  4. If the left child's value matches the next value in the voyage or there is no left child, we traverse the left subtree first, followed by the right subtree without flipping.

Using this approach, we attempt to align our traversal with the voyage sequence. Whenever we find a mismatch with the left child, we flip the node. If flag ok remains True throughout the traversal, then the voyage sequence can be matched by flipping the nodes collected in the answer list. If ok turned False at any point, it means it is impossible to match the voyage sequence, and we return [-1].

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which data structure is used to implement priority queue?

Solution Approach

The solution to this problem is based on the [Depth-First Search](/problems/dfs_intro) (DFS) algorithm. This algorithm is a recursive approach to traverse a tree which fits perfectly with our need to explore each node in the context of the voyage sequence. Letโ€™s dive into the solution implementation using the DFS traversal pattern.

Firstly, a nested function named dfs is defined, which will be used to traverse each node of the tree. This function takes a single parameter root, referring to the current node being visited.

The algorithm uses a few external variables which are not part of the function parameters:

  • i, which is an index keeping track of the current position in the voyage sequence.
  • ok, which is a flag that tracks whether the pre-order traversal has been successful so far.
  • ans, which is a list where the values of flipped nodes are stored.

Here are the main steps taken during the DFS algorithm:

  1. Base Condition: If we reach a None node or if the ok is already False (meanwhile-found mismatch), we return immediately, as there's nothing left to traverse.

  2. Match Check: We check if the current node's value matches the voyage sequence at the index i. If not, we set ok to False and return, since we cannot proceed further with a mismatch.

  3. Pre-order Traversal:

    • We increment i to move to the next element in the voyage sequence after successful matching.
    • If there is no left child or the left child's value matches the next expected value in the voyage sequence, we first traverse left (dfs(root.left)) then right (dfs(root.right)).
    • If the left child does not match the next element in voyage, we must flip the current node to try and match the voyage sequence. We add the value of the current node to the ans list. Then we traverse right (dfs(root.right)) followed by left (dfs(root.left)) since we are considering the left and right children flipped.

Finally, after we initiate the dfs with root as the starting node, once the DFS completes, there are two possible outcomes based on the ok flag:

  • If ok is True, we successfully followed the voyage sequence (potentially with some flips), and we return the ans list, which contains the values of all flipped nodes.
  • If ok is False, we encountered a situation where no flipping could result in matching the voyage sequence, and therefore we return [-1].

With the above implementation, we utilize the DFS algorithm to attempt to make the actual tree's pre-order traversal align with the voyage sequence while keeping track of any flipping needed along the way.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's consider a binary tree example to illustrate the solution approach. Suppose we have a binary tree represented as:

1    1
2   / \
3  2   3

and we're given a voyage sequence [1, 3, 2]. We want to determine if we can achieve this pre-order traversal sequence by flipping nodes in the tree.

  1. We begin at the root with the value 1. This matches the first element of voyage, so no action is needed. We set i to 0 and increment it after the match.

  2. Next, we check the left child of the root. However, our voyage sequence expects the value 3 instead of the current left child value 2. This indicates that we need to flip the root node to match the next element of voyage. We add the root's value 1 to the ans list.

  3. We flip the children nodes of the root and proceed with the right child first (which used to be the left child). The right child's value 2 does not match the next voyage value 3, so we set ok to False. However, we've just flipped the nodes, so we continue the traversal assuming the children are reversed.

  4. We move to the left child (which used to be the right child) with the value 3. This matches the next element in the voyage sequence, so we proceed and increment i.

  5. With all nodes visited and matched after the flip, we check the ok flag. It remains True since we managed to match the voyage sequence with only one flip.

  6. At this point, we've completed the DFS traversal, and since the ok flag is True, we return the list [1], which represents the value of the node we flipped.

The outcome [1] indicates that by flipping the root node, we could achieve the given voyage sequence [1, 3, 2] in the pre-order traversal of the tree.

This simple example clearly illustrates how the DFS approach can be used to decide whether a binary tree's nodes could be flipped to match a given pre-order traversal sequence, and to record which nodes to flip if possible.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
10        # Helper function to perform depth-first search traversal
11        def dfs(node):
12            # Use nonlocal to modify variables defined outside the nested function
13            nonlocal index, is_voyage_matched
14            # If we reach None or the voyage has already failed to match, return
15            if node is None or not is_voyage_matched:
16                return
17          
18            # If the current node's value doesn't match the voyage at the current index, the voyage doesn't match
19            if node.val != voyage[index]:
20                is_voyage_matched = False
21                return
22          
23            index += 1  # Move to the next index in the voyage list
24          
25            # If the left child is present and its value matches the next value in the voyage list, explore left then right
26            if node.left and node.left.val == voyage[index]:
27                dfs(node.left)
28                dfs(node.right)
29            else:  # If there's a mismatch, we must flip the left and right children, record the node, and explore right then left
30                flips.append(node.val)  # Record the flip
31                dfs(node.right)
32                dfs(node.left)
33
34        flips = []  # Stores the list of flipped nodes
35        index = 0   # Tracks the current index in the voyage list
36        is_voyage_matched = True  # Flag to determine if the voyage matches the binary tree
37
38        # Start DFS traversal from the root
39        dfs(root)
40        # Return the list of flips if voyage matched; otherwise, return [-1]
41        return flips if is_voyage_matched else [-1]
42
1class Solution {
2    private int currentIndex; // to keep track of current index in voyage
3    private boolean isPossible; // flag to check if the flip is possible
4    private int[] voyageArray; // the traversal array to match with tree traversal
5    private List<Integer> flippedNodes = new ArrayList<>(); // list to keep track of flipped nodes
6
7    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
8        this.voyageArray = voyage;
9        isPossible = true; // initially assume flip is possible
10        traverseTree(root);
11        // if flip is not possible, return list containing only -1
12        return isPossible ? flippedNodes : List.of(-1);
13    }
14
15    private void traverseTree(TreeNode node) {
16        // if the current node is null or flip is already impossible, stop traversal
17        if (node == null || !isPossible) {
18            return;
19        }
20        // if current node's value does not match current voyage value, set flip as impossible
21        if (node.val != voyageArray[currentIndex]) {
22            isPossible = false;
23            return;
24        }
25        currentIndex++; // move to the next element in voyage
26        // check if left child exists and matches next voyage value, if not, flip is needed
27        if (node.left == null || node.left.val == voyageArray[currentIndex]) {
28            // if no flip needed or left child matches, continue with left subtree
29            traverseTree(node.left);
30            // then traverse right subtree
31            traverseTree(node.right);
32        } else {
33            // flip needed, add current node value to flippedNodes list
34            flippedNodes.add(node.val);
35            // since we flip, we traverse right subtree before left subtree
36            traverseTree(node.right);
37            traverseTree(node.left);
38        }
39    }
40}
41
1#include <vector>
2#include <functional>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode(int x = 0, TreeNode *left = nullptr, TreeNode *right = nullptr) 
10        : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // This function flips the nodes of the tree to match the given voyage and returns
16    // the values of nodes flipped. If impossible, returns {-1}.
17    std::vector<int> flipMatchVoyage(TreeNode* root, std::vector<int>& voyage) {
18        bool isVoyagePossible = true;  // To keep track if the voyage is possible
19        int currentIdx = 0;            // Index to keep track of the current position in the voyage vector
20        std::vector<int> results;      // Vector that will contain the values of the flipped nodes
21      
22        // Lambda function for depth-first search
23        std::function<void(TreeNode*)> dfs = [&](TreeNode* node) {
24            if (!node || !isVoyagePossible) {  // If node is null or voyage so far is impossible, end DFS
25                return;
26            }
27            if (node->val != voyage[currentIdx]) {  // If node's value doesn't match the current voyage value
28                isVoyagePossible = false;           // It's not possible to achieve the voyage
29                return;
30            }
31            ++currentIdx;  // Move to the next index in the voyage vector
32          
33            // Determine if we can continue with left child or need to flip
34            if (node->left && node->left->val != voyage[currentIdx]) {
35                results.push_back(node->val); // Flip the current node
36                dfs(node->right);             // Attempt the right child next
37                dfs(node->left);              // Then the left child last, since we flipped
38            } else {
39                dfs(node->left);              // Attempt the left child next
40                dfs(node->right);             // Then the right child
41            }
42        };
43      
44        dfs(root);  // Start DFS with the root node
45      
46        // If the voyage is possible, return results; otherwise, return {-1}
47        return isVoyagePossible ? results : std::vector<int>{-1};
48    }
49};
50
1// TypeScript definition for a binary tree node.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Returns a list of values in the order of flipped nodes required to match
10 * the given voyage or [-1] if it is impossible.
11 * @param root - The root of the binary tree.
12 * @param voyage - The desired pre-order traversal (voyage) of the tree.
13 * @returns A list of the values of the flipped nodes, or [-1] if impossible.
14 */
15function flipMatchVoyage(root: TreeNode | null, voyage: number[]): number[] {
16  let isPossible = true; // Flag to track if a matching voyage is possible.
17  let currentIndex = 0; // Index to track the current position in the voyage.
18  const flippedNodes: number[] = []; // List to store flipped node values.
19
20  /**
21   * Depth-first search helper function to attempt flipping to match voyage.
22   * @param node - The current node being visited in the tree.
23   */
24  function dfs(node: TreeNode | null): void {
25    if (!node || !isPossible) {
26      // Stop processing if we reach a null node or if it's already impossible.
27      return;
28    }
29  
30    if (node.val !== voyage[currentIndex++]) {
31      // If the current node's value doesn't match the current voyage value, it's impossible.
32      isPossible = false;
33      return;
34    }
35
36    // Check if the current left child is the next in the voyage, or if we need to flip.
37    if (node.left && node.left.val !== voyage[currentIndex]) {
38      // If the left child's value doesn't match, we flip the node.
39      flippedNodes.push(node.val);
40      dfs(node.right); // Visit the right child first since we flipped.
41      dfs(node.left); // Next, visit the left child.
42    } else {
43      // If the left child matches or is null, traverse normally.
44      dfs(node.left);
45      dfs(node.right);
46    }
47  }
48
49  dfs(root); // Start the DFS traversal from the root.
50  return isPossible ? flippedNodes : [-1]; // Return the result based on the isPossible flag.
51}
52
53// You can now use the flipMatchVoyage function by providing the root of a tree and the voyage array.
54
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The code defines a recursive function dfs to traverse the binary tree. Given n as the number of nodes in the tree, the analysis is as follows:

Time Complexity:

  • Each node in the binary tree is visited exactly once in the worst-case scenario.
  • For each node, the algorithm performs a constant amount of work, checking node values and possibly appending to the ans list.
  • Consequently, the time complexity of the dfs function is O(n).

Thus, the overall time complexity of the flipMatchVoyage function is O(n).

Space Complexity:

  • The space complexity includes the space taken by the ans list and the implicit call stack due to recursion.
  • In the worst case, we might need to flip all nodes, so the ans list could potentially grow to O(n).
  • The space complexity due to the recursion call stack is also O(n) in the worst case (this occurs when the tree is completely unbalanced, e.g., a linked list).

Combining both aspects, the total space complexity is O(n) due to the list and recursion stack.

Therefore, the space complexity of the flipMatchVoyage function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ