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, flatten the tree into a "linked list" in-place. The linked list should use the same TreeNode class where the right child pointer points to the next node 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.

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: []
Sample Input
—
Sample Output
—
Constraints
  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100
Test Cases
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.

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