DSA · Trees · #76
Flatten Binary Tree to Linked List
Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given the `root` of a binary tree, flatten it into a "linked list" **in-place**. The linked list should use the same `TreeNode` objects, where the `right` child pointer points to the next node in the list and the `left` child pointer is always `null`. The list should be in the same order as a **pre-order traversal** of the binary tree. Each node has shape `{ val, left, right }`. Implement `function flatten(root)`. It mutates the tree in place and returns nothing (`undefined`).
Examples
root = [1,2,5,3,4,null,6]→[1,null,2,null,3,null,4,null,5,null,6]— Pre-order is 1,2,3,4,5,6; every node's left becomes null and right chains to the next.root = []→[]— An empty tree stays empty.root = [0]→[0]— A single node is already a flattened list.
Constraints
- · The number of nodes in the tree is in the range [0, 2000].
- · -100 <= Node.val <= 100
- · Must mutate the tree in place; the function returns undefined.
- · After flattening, every node's left pointer must be null.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.