Flip Binary Tree To Match Preorder Traversal - Solution & Explanation
Problem Statement
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. For example, flipping node 1 will have the following effect:
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].
Example 1:
Input: root = [1,2], voyage = [2,1] Output: [-1] Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
Example 2:
Input: root = [1,2,3], voyage = [1,3,2] Output: [1] Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.
Example 3:
Input: root = [1,2,3], voyage = [1,2,3] Output: [] Explanation: The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.
Constraints:
- The number of nodes in the tree is
n. n == voyage.length1 <= n <= 1001 <= Node.val, voyage[i] <= n- All the values in the tree are unique.
- All the values in
voyageare unique.
Approach Overview
Problem Overview: You receive a binary tree and an array representing a desired preorder traversal. The task is to flip certain nodes (swap left and right children) so the tree's preorder traversal matches the given sequence. If it is impossible, return [-1]. Otherwise, return the list of node values where flips occurred.
Approach 1: Recursive Pre-order Traversal with Flipping (Time: O(n), Space: O(h))
This method simulates a normal preorder traversal (root → left → right) while comparing each visited node with the next value in the voyage array. Maintain an index pointer that tracks which element of the voyage should appear next. When visiting a node, check if its value matches the current voyage value. If the left child does not match the next expected value but the right child does, a flip is required. Record the node value and traverse the right child before the left. This approach works because preorder traversal order is strictly defined, so detecting a mismatch immediately tells you whether a flip can correct it. If neither child matches the next expected value, the traversal cannot be fixed and you return [-1]. The recursion depth equals the tree height, giving O(h) auxiliary space. This technique relies on standard depth-first search over a binary tree.
Approach 2: Iterative Pre-order Traversal with Stack (Time: O(n), Space: O(n))
An iterative version performs the same preorder simulation but replaces recursion with an explicit stack. Push nodes as you traverse and compare them against the voyage index. When a node's left child does not match the next expected value but the right child does, record the flip and push children in reversed order so traversal processes the correct branch first. Stack-based traversal avoids recursion limits and mirrors how preorder traversal works internally. Each node is pushed and popped at most once, keeping the runtime O(n). Space usage becomes O(n) in the worst case due to the stack storing nodes of a skewed tree. This version is useful when recursion depth might be large or when you prefer explicit control of traversal logic in a tree structure.
Recommended for interviews: The recursive preorder DFS is the most natural solution. It directly models the preorder definition and quickly detects when a flip is required. Interviewers typically expect the O(n) DFS approach with a global voyage index because it shows clear reasoning about traversal order and tree structure.
Approach 1: Recursive Pre-order Traversal with Flipping
The idea is to use a recursive approach that performs a pre-order traversal, comparing each visited node with the corresponding value in the voyage sequence. If the current node's value doesn't match, it may be necessary to flip its children and recheck. The goal is to flip the minimum number of nodes such that the tree's pre-order traversal matches the given voyage. If impossible, return [-1].
This solution uses a depth-first search (dfs) recursively to perform a pre-order traversal. First, iterate through the tree with dfs, comparing each current node's value with voyage[i]. If values match, increment the index. When a node is reached whose left child's value does not match the next required voyage entry, flip its children. If no flips can result in an appropriate traversal, return [-1]. Store and return all nodes whose children were flipped.
Code
Python
JavaScript
Complexity
Time Complexity: O(n) since we traverse all nodes in the binary tree once.
Space Complexity: O(h) due to the recursion call stack, where h is the height of the tree.
Approach 2: Iterative Pre-order Traversal with Stack
This approach uses an explicit stack to simulate a pre-order traversal iteratively and checks against the voyage. The stack helps process nodes similar to recursion, with flipping decisions based on discrepancies between expected and current values.
This solution uses an iterative approach to traverse the tree pre-order using a stack. Nodes are pushed on the stack to be processed later. If the node's value doesn't match the current index in voyage, we return [-1]. If the right child's value equals the next entry in voyage, consider flipping the children if a left child exists, and add the flipped node to res. Push children in an order that aligns with the traversal aimed for by voyage.
Complexity
Time Complexity: O(n) since each node is processed once.
Space Complexity: O(h) where h is the height of the binary tree. The stack size is determined by the deepest path.
Approach 3: DFS
We can traverse the entire tree using depth-first search, using an index i to record the current node's index in the voyage array. If the value of the current node does not equal voyage[i], it means that it is impossible to match after flipping, we mark ok as false and return immediately. Otherwise, we increment i by 1, then check if the current node has a left child. If it does not, or if the value of the left child equals voyage[i], we recursively traverse the current left and right children; otherwise, we need to flip the current node and then recursively traverse the current right and left children.
After the search, if ok is true, it means that it is possible to match after flipping, and we return the answer array ans, otherwise, we return [-1].
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Pre-order Traversal with Flipping | Time Complexity: O(n) since we traverse all nodes in the binary tree once. |
| Iterative Pre-order Traversal with Stack | Time Complexity: O(n) since each node is processed once. |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Pre-order Traversal with Flipping | O(n) | O(h) | Best general solution. Clean logic that directly follows preorder traversal rules. |
| Iterative Pre-order Traversal with Stack | O(n) | O(n) | Useful when avoiding recursion or handling very deep trees. |
Video Solution
Flip Binary Tree To Match Preorder Traversal | Live Coding with Explanation | Leetcode - 971 • Algorithms Made Easy • 3,051 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Flip Binary Tree To Match Preorder Traversal easy or hard?
Flip Binary Tree To Match Preorder Traversal Python/Java solution
How to solve Flip Binary Tree To Match Preorder Traversal in O(n)?
What is the best approach for Flip Binary Tree To Match Preorder Traversal?
Is Flip Binary Tree To Match Preorder Traversal asked at Google/Amazon/Meta?
What data structure is used in Flip Binary Tree To Match Preorder Traversal?
What is the time complexity of Flip Binary Tree To Match Preorder Traversal?
Ready to solve this problem?
Practice Flip Binary Tree To Match Preorder Traversal with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor