Recursive solution to flatten binary tree to linked list

Question

Here is the link for problem description: Flatten Binary Tree to Linked List has:

# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """

The solution is:

class Solution:

    def flattenTree(self, node):

        # Handle the null scenario
        if not node:
            return None

        # For a leaf node, we simply return the
        # node as is.
        if not node.left and not node.right:
            return node

        # Recursively flatten the left subtree
        leftTail = self.flattenTree(node.left)

        # Recursively flatten the right subtree
        rightTail = self.flattenTree(node.right)

        # If there was a left subtree, we shuffle the connections
        # around so that there is nothing on the left side
        # anymore.
        if leftTail:
            leftTail.right = node.right
            node.right = node.left
            node.left = None

        # We need to return the "rightmost" node after we are
        # done wiring the new connections.
        return rightTail if rightTail else leftTail

    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        self.flattenTree(root)

I don't understand this block of code:

        if leftTail:
            leftTail.right = node.right (step 1)
            node.right = node.left      (step 2)
            node.left = None

For example, if the binary tree input is [1, 2, 3], the leftTail after step 1 will be: [2, null, 3]. My naive thought is after step 2, the tree becomes [1, null, 3] but to my surprise, it becomes: [1,null,2,null,3].

It means 1 is the parent node, 2 and 3 are left and right children respectively. TreeNode{val: 1, left: TreeNode{val: 2, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}} — superStar, Jun 27 '22 at 22:24

score 1 · Accepted Answer · answered Jun 27 '22 at 23:30

1

Suppose your example with tree [1, 2, 3]:

  1 (node)
 / \
2   3

And lets check what was done by every step:

if leftTail:
    leftTail.right = node.right (step 1)
    node.right = node.left      (step 2)
    node.left = None            (step 3)

Step 1:

  1 (node)
 / \
2   3
 \
  3 (same as above)

Step 2:

  1 (node)
 / \
2   2 (same as left)
 \   \
  3   3

Step 3:

  1 (node)
   \
    2
     \
      3

So, [1, null, 2, null, 3] is achieved.

answered Jun 27 '22 at 23:30

klimenkov

347
2
8

Thank you very much for your help. I still don't understand why node.left was changed after step 1? In step 1, leftTail was changed but why did that result in the change in node.left? – superStar Jun 27 '22 at 23:34
Because `leftTail = self.flattenTree(node.left)` for this specific case is exactly `node.left`, as it is a leaf (`self.flattenTree(node.left)` just returns its argument). – klimenkov Jun 27 '22 at 23:39
I see, it is kind of super confusing to me. LeftTail was assigned the value of node.left, but I don't know why the change in left Tail resulted in the change in node itself? Is it similar to pointer in C language? In my normal way of thought, For example Step 1 : c = 3, Step 2 : a = c, Step 3: a =2 . In this case, a is changed to 2 but c still 3 – superStar Jun 27 '22 at 23:45
Shouldn't it be `[1, null, [2, null, 3]]`? – Scott Hunter Jun 27 '22 at 23:47
@superStar you are absolutely right, in this context the variable behaves exactly like a pointer. And your example should be rewritten as: 1: c = [3], 2: a = c, 3: a.append(2), so both variables _are pointing_ to the same value. You may check this link: https://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference – klimenkov Jun 28 '22 at 08:37
@ScottHunter leetcode just uses a list of nodes after bfs traversal (row by row) – klimenkov Jun 28 '22 at 08:41

Recursive solution to flatten binary tree to linked list

1 Answers1