971. Flip Binary Tree To Match Preorder Traversal
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]
.
Flowchart Walkthrough
To analyze the LeetCode problem 971. Flip Binary Tree To Match Preorder Traveral with the Flowchart, let's go through the decision steps based on the provided algorithm flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: Even though the problem is about a binary tree, in computational terms, a tree is a type of acyclic graph.
Is it a tree?
- Yes: Specifically, the problem is dealing with a binary tree structure.
DFS
- Next step: Since the structure in question is a tree, the flowchart specifically recommends Depth-First Search (DFS) for such scenarios.
Conclusion: Per the flowchart, for problems involving traversal or modification of trees, utilizing DFS is appropriate. In this problem, where we have to traverse the tree in a specific manner and possibly alter some nodes (flip operations) to match a given preorder, DFS is an effective method to explore each node and make the necessary changes in a depth-first fashion.
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:
- If the current node is
None
, we just return as there's nothing to process. - If the current node's value does not match the
voyage
sequence at indexi
, it means it's impossible to achieve the desired pre-order by flipping nodes. In this case, we set a flag (ok
) toFalse
. - 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. - 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.
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 thevoyage
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:
-
Base Condition: If we reach a
None
node or if theok
is alreadyFalse
(meanwhile-found mismatch), we return immediately, as there's nothing left to traverse. -
Match Check: We check if the current node's value matches the
voyage
sequence at the indexi
. If not, we setok
toFalse
and return, since we cannot proceed further with a mismatch. -
Pre-order Traversal:
- We increment
i
to move to the next element in thevoyage
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 thevoyage
sequence. We add the value of the current node to theans
list. Then we traverse right (dfs(root.right)
) followed by left (dfs(root.left)
) since we are considering the left and right children flipped.
- We increment
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
isTrue
, we successfully followed thevoyage
sequence (potentially with some flips), and we return theans
list, which contains the values of all flipped nodes. - If
ok
isFalse
, we encountered a situation where no flipping could result in matching thevoyage
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
We begin at the root with the value
1
. This matches the first element ofvoyage
, so no action is needed. We seti
to 0 and increment it after the match. -
Next, we check the left child of the root. However, our
voyage
sequence expects the value3
instead of the current left child value2
. This indicates that we need to flip the root node to match the next element ofvoyage
. We add the root's value1
to theans
list. -
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 nextvoyage
value3
, so we setok
toFalse
. However, we've just flipped the nodes, so we continue the traversal assuming the children are reversed. -
We move to the left child (which used to be the right child) with the value
3
. This matches the next element in thevoyage
sequence, so we proceed and incrementi
. -
With all nodes visited and matched after the flip, we check the
ok
flag. It remainsTrue
since we managed to match thevoyage
sequence with only one flip. -
At this point, we've completed the DFS traversal, and since the
ok
flag isTrue
, 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
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 isO(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 toO(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.
Which data structure is used in a depth first search?
Recommended Readings
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
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 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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.