Follow the process of exploring tree structures and implementing various binary tree problems.

Coding

Traverses a tree by exploring as deeply as possible along each branch before backtracking, which is useful for tasks like traversal, pathfinding, or search operations.

Tree Depth-First Search

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# Statement
Given the `root` of a binary tree, the task is to flatten the tree into a linked list using the same `TreeNode` class. The left child pointer of each node in the linked list should always be NULL, and the right child pointer should point to the next node in the linked list. The nodes in the linked list should be in the same order as that of the preorder traversal of the given binary tree.

**Constraints:** 

* $-100 \leq$ `Node.data` $\leq 100$.
* The tree contains nodes in the range $[1, 500]$.

# Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

## Naive approach

The naive approach to flatten a binary tree into a linked list is to perform a preorder traversal of the tree and store the visited nodes in a Queue. After the traversal, start dequeuing the nodes and set the pointers of each node such that: the right pointer of the dequeued node is set to the previously dequeued node, and the left pointer is set to NULL.

However, this naive approach requires extra memory because it uses a Queue. The space complexity would be $O(n)$. However, can the problem be solved without additional data structures?

## Optimized approach using depth-first search 


The solution to flattening a binary tree into a linked list involves a depth-first traversal to rearrange the tree’s nodes in place. The process begins by recursively flattening the left and right subtrees. The left subtree is attached to the current node’s right, and the original right subtree is appended to the end of this newly attached left subtree. Following this pattern for each node, the tree is transformed into a singly linked list with all nodes arranged in the same order as a pre-order tree traversal. This ensures the final structure retains a linear chain of nodes without additional space.

Specifically, we start at the root node, and for each node, find the right-most node in its left subtree. We set the right pointer of the right-most node to the current node's right pointer. After that, we set the current node's right pointer to the current node's left pointer. Finally, we set the current node's left pointer to NULL. We will repeat this process for all nodes in the binary tree.

Let's solve the Flatten Binary Tree to Linked List problem using the Tree Depth-First Search pattern.

Solution: Flatten Binary Tree to Linked List

Statement▼

Solution: Flatten Binary Tree to Linked List

Statement▼