Flatten Binary Tree to Linked List

def flatten(root):
    cur = root
    while cur:
        if cur.left:
            p = cur.left
            while p.right:
                p = p.right
            p.right = cur.right
            cur.right = cur.left
            cur.left = None
        cur = cur.right

Flatten Binary Tree to Linked List. Flatten a binary tree, in place, into one chain: each right pointer leads to the next node in preorder, and every left pointer is empty. Here, each node is a monkey, holding one below with each hand.

Take this tree: one holds two and five; two holds three and four; five holds six. In preorder, that's one through six, so the chain hangs in that order, left hands free.

The easy way lists the nodes in preorder, then relinks them. But that list costs order n extra space.

The key idea: rewire in place. At a node with a left child, find the rightmost node on its left side. Hang the node's right side from it, swing the left side over to the right, and let go on the left. Then step right.

In code, a pointer starts at the root. With a left child, walk right to the end, attach the right subtree, move left to right, and clear left. Then move right.

Let's walk it. At one, the left side's rightmost is four: five hangs from four, and two swings right. At two, the rightmost is three: four hangs from three, and three swings right. Three, four, five and six have no left child, so we step. One chain.

Each link is walked at most twice: order n time, and two pointers: order one space. A recursion in reverse preorder also works, but its stack costs the height.

Find the rightmost, hang the right, swing the left. That's Flatten Binary Tree to Linked List.