Question

link

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
Hints:

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

Stats

Frequency 3
Difficulty 3
Adjusted Difficulty 4
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very difficult question, and there are many solutions.

Solution

Analysis of all solutions (except first one) is found in this great article.

Solution 1 is my code, I am make use of a ‘pre’ pointer in this recursive method. This idea is actually quite good, but is never seen in any other people’s blogs.

Solution 2 is the most standard recursive solution. It passes in a node, flatten it and return the last node after it’s flattened. So we can flatten root node’s left and right node respectively, and then connect it.

To flatten a binary tree, according to the given example, is to recursively insert the left subtree to the right subtree and append the original right subtree to the end of the left subtree, i.e.
     root                        root
     /  \            ->            \
  left  right                      left
                                     \
                                    right
Since we need to append the original right-tree to the end of the left subtree, we let the recursion function return the last node after flatten.

I missed “root.left = null” while coding, and it resulted in long long time debugging. I think this is a very silly mistake.

Solution 3 is making use of a stack. I have to say, although I can figure how it works, I am still blur about the thinking process of this entire idea. Which is to say, I can’t keep it in mind even after learning it.

I shall try write this code in the future.

We can also solve the problem without recursion.

To do that, we can use a stack to store all right subtrees when we prune them temporarily, and append each of them back after we go through the corresponding left subtree.

Basically, given a non-empty tree,
  • if it has left subtree, store the right subtree (if not null) to stack, move the left subtree to right;
  • if not, append back a subtree from stack to the current node's right;
  • continue to the right node until finish.

Solution 4 is what I believe the best solution. It simple uses while loop to put all nodes in the correct position, without recursion or stack.

Each time when we prune a right subtree, we use while-loop to find the right-most leaf of the current left subtree, and append the subtree there.

Analysis of all solutions (except first one) is found in this great article.

Code

First, my solution, a kind of recursive solution

public void flatten(TreeNode root) {
    helper(new TreeNode(1234), root);
}

private TreeNode helper(TreeNode pre, TreeNode node) {
    // pre cannot be null, this function return the last node of the flatten list
    if (node == null) return pre;
    pre.left = null;
    pre.right = node;
    TreeNode a = node.left;
    TreeNode b = node.right;
    TreeNode temp = helper(node, a);
    return helper(temp, b);
}

Second, standard recursive solution

看这里：helper function 的 return value 是 tail node，不是 head node。

public void flatten(TreeNode root) {
    helper(root);
}

private TreeNode helper(TreeNode root) {
    if (root == null) return null;
    TreeNode oldRight = root.right;
    if (root.left != null) {
        root.right = root.left;
        // I missed this line of code:
        root.left = null;
        root = helper(root.right);
    }
    if (oldRight != null) {
        root.right = oldRight;
        root = helper(root.right);
    }
    // return value is the last element of the flatten tree
    return root;
}

Third, stack non-recursive solution

public void flatten(TreeNode root) {
	TreeNode cur = root;
	Stack<TreeNode> rtrees = new Stack<TreeNode>();
	while (cur != null) {
		while (cur.left != null) {
			if (cur.right != null)
				rtrees.push(cur.right);
			cur.right = cur.left;
			cur.left = null;
			cur = cur.right;
		}
		if (cur != null && cur.right == null && !rtrees.isEmpty()) {
			cur.right = rtrees.pop();
		}
		cur = cur.right;
	}
}

Fourth, non-stack non-recursive solution

public void flatten(TreeNode root) {
	TreeNode cur = root;
	while (cur != null) {
		if (cur.left != null) {
			if (cur.right != null) { // if we need to prune a right subtree
				TreeNode next = cur.left;
				while (next.right != null)
					next = next.right;
				next.right = cur.right;
			}
			cur.right = cur.left;
			cur.left = null;
		}
		cur = cur.right;
	}
}