Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.

Problem statement

Given the root of a binary tree, flatten the tree into a "linked list":

- The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

- The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [0] Output: [0]

Constraints:

- The number of nodes in the tree is in the range [0, 2000].

- -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Topics and companies

Topics: Linked List, Stack, Tree, Depth-First Search, Binary Tree.

Reported in interviews at Facebook, Microsoft, Amazon.

How to practise Flatten Binary Tree to Linked List on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the number of nodes in the tree. Each node is visited exactly once. time and O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N. space.

Open Flatten Binary Tree to Linked List in the code editor, or read the Flatten Binary Tree to Linked List editorial for a worked solution with its approach and complexity analysis.

Where Flatten Binary Tree to Linked List sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Preorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Flatten Binary Tree to Linked List

Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• Binary Tree Paths — Easy, same subpattern
• Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
• Invert Binary Tree — Easy, same subpattern
• Same Tree — Easy, same subpattern
• Smallest String Starting From Leaf — Medium, same subpattern
• Symmetric Tree — Easy, same subpattern