Flatten Binary Tree to Linked List Medium 0 attempts
LeetCode ↗

Flatten Binary Tree to Linked List

Medium TreeBinary TreeDFS LeetCode

Given the root of a binary tree, rearrange it in-place into a "linked list" built from the same TreeNode structure: every node's left pointer becomes null, and its right pointer leads to the next node in the sequence. The resulting order of nodes should match what a pre-order traversal of the original tree would produce.

Input Format
Implement flattenBinaryTreeToLinkedList(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Modify the input tree in place. The editor checks the original root after the call and displays its level-order array; return values are ignored.

Sample Input and Output

Example 1 ยท Run Sample

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
[]
Constraints
  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100
Test Cases (2)
Case 1
Args: [[1,2,5,3,4,null,6]] Expected: [1,null,2,null,3,null,4,null,5,null,6]
Case 2
Args: [[]] Expected: []
Topics
TreeBinary TreeDFS

Approach: Morris-like Traversal

For each node with a left child, find the rightmost node of the left subtree. Connect that rightmost node to the current right child. Then move the entire left subtree to the right side and set left to null. Advance to the next right node.

javascript
function flattenBinaryTreeToLinkedList(root) {
  let curr = root;
  while (curr) {
    if (curr.left) {
      let prev = curr.left;
      while (prev.right) prev = prev.right;
      prev.right = curr.right;
      curr.right = curr.left;
      curr.left = null;
    }
    curr = curr.right;
  }
  return root;
}

Time Complexity: O(n)

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript