## Similar Problems

Similar Problems not available

# Flip Binary Tree To Match Preorder Traversal - Leetcode Solution

## Companies:

LeetCode: Flip Binary Tree To Match Preorder Traversal Leetcode Solution

Difficulty: Medium

Topics: tree binary-tree depth-first-search

Problem Statement:
Given the `preorder`

traversal sequence of a binary tree, we need to check if it is possible to flip any of the nodes in the binary tree to create the same `preorder`

traversal sequence.

If it is possible, then we need to return a list of values of flip operations that can be performed on the binary tree.

If it is not possible, then we need to return a list containing only `-1`

.

A `flip`

operation on a node means to swap its left and right children.

Solution Approach: We can solve this problem using a recursive depth-first search (DFS) approach.

The root of the binary tree will always be the first value in the `preorder`

traversal sequence, and we can use this to traverse the tree recursively.

We will keep track of the current index of the `preorder`

traversal sequence as we traverse the tree recursively.

For each node in the tree, we will check if its value matches the current value in the `preorder`

traversal sequence. If it does not match, then we cannot flip any nodes to create the same `preorder`

traversal sequence, and we will return a list containing only `-1`

.

If it does match, we will continue to the left and right children of the node, recursively.

If the `preorder`

traversal sequence at the current index matches the value of the left child, we do not need to perform any flip operations on this node, so we will continue the recursion on the left child.

If the `preorder`

traversal sequence at the current index matches the value of the right child, we need to perform a flip operation on the current node. We will add the value of the current node to the list of flip operations, and then swap the left and right children of the current node.

We will then continue the recursion on the flipped right child (which was the original left child).

At the end of the recursion, if we have reached the end of the `preorder`

traversal sequence and all nodes have matched, then we can return the list of flip operations.

If we have not matched the entire `preorder`

traversal sequence, then we cannot flip any nodes to create the same `preorder`

traversal sequence, and we will return a list containing only `-1`

.

Solution Steps:

- Initialize an empty list
`flips`

to keep track of flip operations. - Initialize a variable
`index`

to`0`

, to keep track of the current index in the`preorder`

traversal sequence. - Traverse the binary tree recursively using DFS. For each node:
- If the value of the node does not match the value of the current index in the
`preorder`

traversal sequence, return a list containing only`-1`

. - If the
`preorder`

traversal sequence at the current index matches the value of the left child, continue the recursion on the left child. - If the
`preorder`

traversal sequence at the current index matches the value of the right child:- Append the value of the current node to
`flips`

. - Swap the left and right children of the current node.
- Continue the recursion on the flipped right child (which was the original left child).

- Append the value of the current node to
- Increment
`index`

after each recursive call.

- If the value of the node does not match the value of the current index in the
- If the entire
`preorder`

traversal sequence has been matched, return`flips`

. - Otherwise, return a list containing only
`-1`

. - The time complexity of this solution is
`O(n)`

, where`n`

is the number of nodes in the binary tree.

## Flip Binary Tree To Match Preorder Traversal Solution Code

`1`