Flatten Binary Tree to Linked List

[kokocan12]

Problem

When a root node of binary tree is given, flatten the binary tree to linked list.
Linked list means that every nodes of the tree connected through the right child.
Linked list should be ordered in pre-order(head first, then left, right direction)

Approach

We can divide tree to three parts. (head, left, right)

Then, flatten left first, connect the right part to the last item of the flattened left part.

The code is below.

function travel(root) {
    if(root === null) return null;
    
    const tempLeft = root.left;
    const tempRight = root.right;
    root.left = null;
    root.right = travel(tempLeft);
    const rightEnd = reachToRightEnd(root);
    rightEnd.right = travel(tempRight);
    
    return root;
}

function reachToRightEnd(node) {
    if(node === null) return node;
    
    while(node.right !== null) {
        node = node.right;
    }
    
    return node;
}