# A VERY VERY detailed explanation of the highest-voted solution and some interesting thoughts about it.

• Lemme try to explain @tusizi 's idea a little bit, based on his code snippet.

As you can see, the problem asks for a linkedlist-alike result. To build a linked list recursively, let's say we have reached recursion depth `d`, we need to set the current node `cur` 's next attribute as the return value of recursion call `d+1`. And we return `cur`, which will be used in `d-1` recursion. Pretty much like that.

Similarly, for this problem, we also need to find the current node's next node. For this problem, we use `TreeNode prev` to hold the next node (I must say, I'd prefer it is named as `next` or something.) The difference from above is that, instead of returning the next node, @tusizi uses a global variable to maintain the next node. The reason will be stated in the following. But I have point out, I agree with @cifer-lee , it remains to be discussed if it is a good way for doing so, but for now let's just assume it is. In the following, I will use linked list or tree, head or root, right or next, interchangeably.

Let's inspect the execution process of @tusizi 's code snippet a little bit.

``````private TreeNode prev = null;

public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
``````

After `flatten(root.right)`, we have processed the right branch of the current node, and the current `prev` is the head of root of the right branch. For now, we want to know which node is the precedent node of `prev`, and we will set this particular node's next attribute as `prev`. As per the problem, this particular node is actually the rightmost node of the left branch.

Next, let's say why we can actually get it. So now we go to the next line, which is `flatten(root.left)`. When we go deeper and deeper in the recursion, we are actually going right because we go right before we go left. A small remark here, the traversal order of the code snippet is actually `right->left->cur`, not post-order, more like reversed post order if you like. As we are going right, we will stop when we cannot go right furthermore. Then we set right or next attribute of the current node as `prev`, which is exactly what we want.

Now let's go back to the original function call layer, we have done `flatten(root.right)` and `flatten(root.right)`. The remaining is easy, we set the root node's next node as `prev`, which is the head of the left branch. Done!

A little more comment on why we cannot return the current node like what we do in linked list for this solution. The short answer is that tree is non-liner. The more verbose answer is that we want to connect the rightmost node on the left branch to the leftmost node on the right branch, this is something that we cannot achieve in the current layer directly. If we insist on returning value, we may need to traverse the left branch on our own, and then do the same connection stuff. This is what a lot other solutions are doing, like this one hanzhou87's solution. My solution is to return the end node of left branch directly. The following is my solution in Python.

``````class Solution(object):
def flatten(self, root):
if not root:
return

def _helper(node):
r_end = l_end = None
if node.right:
r_start, r_end = _helper(node.right)
if node.left:
l_start, l_end = _helper(node.left)
l_end.right = node.right
node.right = l_start
# Clear left branch
node.left = None

return (node, r_end or l_end or node)

_helper(root)
``````

The following is the python version of the idea.

``````class Solution(object):
prev = None
def flatten(self, root):
if not root:
return
self.flatten(root.right)
self.flatten(root.left)

root.right = self.prev
root.left = None
self.prev = root
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.