Back to DSA

Flatten Binary Tree to Linked List

medium
Acceptance: 54%
Binary TreeLinked List

Transform a binary tree into a singly linked list arranged in pre-order sequence, reusing the existing tree nodes. In the resulting structure, every node's left child pointer is null and its right child pointer leads to the next node in pre-order.

Examples

Example 1:
Input:root = [5,3,8,1,4,null,9]
Output:[5,null,3,null,1,null,4,null,8,null,9]

Hints

Related Problems

Reverse Linked ListeasyLinked List CycleeasyMaximum Depth of Binary TreeeasyInvert Binary TreeeasyPalindrome Linked Listeasy
00:00
class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode rightmost = curr.left;
                while (rightmost.right != null) rightmost = rightmost.right;
                rightmost.right = curr.right;
                curr.right = curr.left;
                curr.left = null;
            }
            curr = curr.right;
        }
    }
}
Time complexityO(n)
Space complexityO(h)