Flatten Binary Tree to Linked List (Java)_ why this recursive code not working?

Leetcode question as below:

Description
Flatten a binary tree to a fake "linked list" in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in ListNode.

Input:{1,2,5,3,4,#,6}

Output：{1,#,2,#,3,#,4,#,5,#,6}

Explanation：

     1
    / \
   2   5
  / \   \
 3   4   6

1
\
 2
  \
   3
    \
     4
      \
       5
        \
         6

code below does not return expected, but could not figure out why:

public class Solution {
     
    public void flatten (TreeNode root){
       TreeNode lastNode = null;
       helper (root, lastNode); 
    }
    
    private void helper(TreeNode root, TreeNode lastNode){
        if (root == null){
            return; 
        }
        
        if(lastNode != null){
            lastNode.left = null; 
            lastNode.right = root; 
        }
        lastNode = root; 
        TreeNode right = root.right;
        helper(root.left, lastNode); 
        helper(right, lastNode); 
        
        
    }
}

test result:
Input
{1,2,5,3,4,#,6}
Output
{1,#,5,#,6}
Expected
{1,#,2,#,3,#,4,#,5,#,6}

Couldn't understand why the output will be {1,#,5,#,6} instead of expected of {1,#,2,#,3,#,4,#,5,#,6}. Can anyone explain?Thanks

You have almost coded it well, but there's a small bug. While writing the code you are assuming that the lastNode is updated to the last node while visiting in pre-order. But that is not the case.

The lastNode variable is still pointing to the current last node, after the recursion call is back at this line helper(right, lastNode); .

Let us take an example. Suppose we are at node 2, so we change the lastNode to node 2 and then call its left child. After the helper(root.left, lastNode); line is executed, we believe that lastNode should point to node 3. But that is not the case, it's still pointing to node 2.

Let's see what the debugger says for the above scenario

What should we do to remove this bug, Just return the lastNode during the recursion call.

See the example code below

private TreeNode helper(TreeNode root, TreeNode lastNode){
        if (root == null){
            return lastNode;
        }

        if(lastNode != null){
            lastNode.left = null;
            lastNode.right = root;
        }
        lastNode = root;
        TreeNode right = root.right;
        lastNode =  helper(root.left, lastNode);
        lastNode =  helper(right, lastNode);
        return lastNode;
}

After the above changes, the result is something like this

private void helper(TreeNode root, TreeNode lastNode){
        if (root == null){
            return; 
        }
        
        if(lastNode != null){
            lastNode.left = null; // *** 1
            lastNode.right = root; // *** 1 
        }
        lastNode = root; 
        TreeNode right = root.right;
        helper(root.left, lastNode); // *** 2
        helper(right, lastNode); // *** 3
    }

In section 1, you attach the left children to the right for this lastNode.
In section 2, you call for the left children, where section 1 will be executed.
In section 3, you call for the right children, where section 1 will be executed.

So when section 2 completes it's work, lastNode will have right children already by calling section 1. When section 3 is called and it performs its own section 1 of the code, it will overwrite the work done in section 2.

What you probably want to do is return the "leaf" in the helper function and use the leaf as the lastNode (i.e. Node 4, instead of root).

	private TreeNode helper(TreeNode root, TreeNode leaf){
	    if (root != null){
	        if (leaf != null){
	        	leaf.left = null; // *** 1
	        	leaf.right = root; // *** 1 
	        }
	        leaf = root;
	        TreeNode right = root.right;
	        leaf = helper(root.left, leaf); // *** 2
	        leaf = helper(right, leaf); // *** 3
	    }
	        
	    return leaf; 
	}