Flatten Binary Tree to Linked List

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree, flatten it **in place** into a right-leaning chain that uses the existing nodes. In the result every node's left pointer is null and its right pointer points to the node that follows it in the tree's **preorder** traversal. Return the root of the flattened tree (the same node as the original root, or null for an empty tree). The grader serializes the returned tree in level order, so a chain looks like [1,null,2,null,3]. Follow-up: can you do it with O(1) extra space?

Examples

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Preorder is 1,2,3,4,5,6, so the chain follows that order.
Input: root = []
Output: []
An empty tree stays empty.
Input: root = [0]
Output: [0]
A single node is already flat.

Constraints

  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems