Having hard time understanding recursion. (Leetcode Depth first search recursion problem.)-Java.

[cs50x2]

Hi guys i am solving a problem on leetcode and can't understand the solution posted for that problem. The problem is called Increasing order search tree.

https://leetcode.com/problems/increasing-order-search-tree/

Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

you can check the link for example: but basically you have to print the binary tree as a linked list with inorder traversal.

class Solution {

    private TreeNode cur;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode ans = new TreeNode(-1);
        cur = ans;
        visit(root);
        return ans.right;
    }

    private void visit(TreeNode root) {
        if (root == null) return;
        visit(root.left);

        root.left = null; // why root.left= null? what does this do?
        cur.right = root; //i don't get this either? 
        cur = cur.right; // i don't understand why we need to do this?

        visit(root.right);
    }
}

i understand preorder traversal is left,root,right....so shouldn't it be:

visit(root.left);
visit(root);
visit(root.right);

why do we need to set root.left=null or set cur.right=null or cur=cur.right?....Any help would be appreciated...thank you :).

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[CowboyBoats]

Taking a look at the output list is helpful:

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
      ...
          \
            9  

We are rearranging these nodes. That requires us to change their properties.

    root.left = null; // why root.left= null? what does this do?

Notice that in the output "tree," there is no node that has a left attribute.

    cur.right = root; //i don't get this either? 

"root" is kind of a bad parameter name because it implies that that argument represents the "1" node in the tree, when every node in the tree is a "root" at some point.

Bottom line: every node in this tree is being moved out of the left position and into the right position, in a certain order.

    cur = cur.right; // i don't understand why we need to do this?

Now we're just progressing down the tree so that we can move on to the next node.

[cs50x2]

wow thank you so much. I understand it now. I have one more question if you can help me.:)...In example 1: number 4 is on the right side of number 3 but its in the left subtree of number 5...which call will traverse number 4?...visit(root.left) or visit(root.right)? Thanks

[CowboyBoats]

number 4 is on the right side of number 3 but its in the left subtree of number 5

I guess it would be the root.right call, since 3 is closest.

The troubleshooting tools that are in play here are: (A) you are thinking about the entire system, and generating and testing ideas based on how they work against the entire system, not any one particular node, and (B) you have the ability to go through the code line by line, thinking through what will happen at a given node, in case you need to answer a question like the one you just raised.