LeetCode: Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

---

Since the next node is the next node of a pre-order traversal, we can solve this recursively. We can convert its right subtree first, and then convert its left subtree. Finally concatenate them all to the right side.

C++ Code:

/*
 * func: flatten_binary_tree_helper
 * goal: recursive helper function to flatten the tree
 * @param root: current root node of the tree
 * return: root node after flatten
 */
TreeNode *flatten_binary_tree_helper(TreeNode *root){
    if(root == nullptr){
        return root;
    }
    
    //Convert right subtree to list
    TreeNode *right_subtree = flatten_binary_tree_helper(root->right);
    
    //Convert left tree to list and concatenate it to the right of the tree
    root->right = flatten_binary_tree_helper(root->left);
    
    root->left = nullptr;
    
    TreeNode *tmp_root = root;
    //Concatenate right subtree
    while(tmp_root->right){
        tmp_root = tmp_root->right;
    }
    
    tmp_root->right = right_subtree;
    
    return root;
}

/*
 * func: flatten_binary_tree
 * goal: flatten a binary tree to a linked list in place
 * @param root: root node of the tree
 * return:
 */
void flatten_binary_tree(TreeNode *root){
    flatten_binary_tree_helper(root);
}

Python Code:

# func: flatten binary tree to a list
# @param root: root node of the tree
# @return:
def flatten_binary_tree(root):
    def flatten_binary_tree_helper(node):
        if not node:
            return node
        #Faltten right subtree first
        right_subtree = flatten_binary_tree_helper(node.right)
        #Faltten left subtree and concatenate it to the right side of the tree
        node.right = flatten_binary_tree_helper(node.left)
        node.left = None
        #Find the spot to concatenate remaining right subtree
        iter = node
        while iter.right:
            iter = iter.right
        iter.right = right_subtree
        return node
    flatten_binary_tree_helper(root)

Reference Link:

1. My Leetcode: Flatten Binary Tree to Linked List (Java): http://rleetcode.blogspot.com/2014/02/flatten-binary-tree-to-linked-list-java.html