← Tree Traversal

Micro-Drill #218 — Flatten BT to linked list

Tree Traversal Target: 15s

Morris-like: for each node with left child, find its inorder predecessor, link right subtree there, move left to right.

def flatten(root):
    cur = root
    while cur:
        if cur.left:
            # find rightmost of left subtree
            prev = cur.left
            while prev.right:
                prev = prev.right
            # rewire
            prev.right = cur.right
            cur.right = cur.left
            cur.left = None
        cur = cur.right

Type it from memory. Go.

Practice Problems

Related Coding Drills

← Micro #217 Micro #219 →