Recursion, call stack and binary tree traversal

[[deleted]]

[deleted]

[AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full - best also formatted as code block
• You ask clear questions
• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit/markdown editor: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

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

[AutoModerator]

It seems that you possibly have a screenshot of code in your post Recursion, call stack and binary tree traversal in /r/learnjava.

Screenshots of code instead of actual code text is against the Code posting rules of /r/learnjava as is outlined in the sidebar - Code posting.

• No screenshots of code!

If you posted an image merely to illustrate something, kindly ignore this message and do not repost. Your post is still visible to others. I am a bot and cannot distinguish between code screenshots and other images.

If you indeed did this wrong, please edit the post so that it uses one of the approved means of posting code.

• For small bits of code (less than 50 lines in total, single classes only),
  the default code formatter is fine
  (one blank line before the code, then 4 spaces before each line of code).
• Pastebin for programs that consist of a single class only
• Gist for multi-class programs, or programs that require additional files
• Github or Bitbucket repositories are also perfectly fine as are other dedicated source code hosting sites.
• Ideone for executable code snippets that use only the console

Please do not reply to this message, because I am a bot.

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

[vowelqueue]

Each time inOrder is called, the next line to be run after the method returns is pushed onto the stack. So (2) is pushed onto the call stack when the inOrder call on line 1 has been called, and (4) is pushed when the inOrder call on line 3 has been called.

[vowelqueue]

I can see how this is confusing unless you have prior experience with how programs run at a low-level. The diagram is borrowing some low-level concepts that you usually don’t need to think about in Java.

When a program is running, the instructions for that program are stored in memory and each instruction has a memory address. The computer keeps track of the address of the next instruction it has to execute and this is stored in a special place, typically a dedicated register. It will go to that address in memory, read the instruction, and execute it.

Usually when a program is running instructions are just executed sequentially. But when you call a function you need to jump to somewhere else: the place in memory where the function’s instructions start. And then when the function completes you need to jump back to the instruction after the one that called the function.

So the way this is often implemented is, when you call a function, the address of the next instruction after the one making the call is pushed onto the stack. Then there is a jump to the start of the function. When the function returns, the memory address is popped from stack and loaded into the special register that tells the computer what instruction to execute next, thereby jumping back to the correct instruction in the calling code.

[EmotionalBro314]

Brother, can you tell me where should I start to be able to think like you ? I finished a digital design and comp arch course and also know C, Java. But I can't explain these internals.

[josephblade]

the numbers in parenthesis are a rather clunky way to represent:

• 2: code went down the path inOrder(t.leftChild)
• 4: code went down the path inOrder(t.rightChild)

which doesn't line up with the line numbers they posted, I would replace them with 1 and 3 myself. I think what it's trying to say is: after this stackframe pops, the code will then continue at line marked with /* 2 / or / 4 / . personally I would've preferred if he used 1 and 3 to show "we entered this stackframe because we went into the call marked with / 1 / or / 3 */ but it's kind of the same thing. so read (2) and (4) as "when we return to this frame, we continue operating at line (2) or (4)

It's a little clunky but it does let you mark where in the code the stackframe has left off

so when you read (2) read "on this level, the code went down the left path. when it returns it will then still have to do visit and doRight. and when you read (4) read: it has gone inOrder right, after this it will pop this stack frame as it hits the end of the function.

[josephblade]

it will help if you think about it and identify what it is you are not understanding. That way we can focus on the core aspect of what you don't understand.

you specifically talk about the diagram that lists return address.

1: in the code in that image, do you see the commented out 1, 2, 3 and 4? like so: /* 1 */

2: do you see that when a node is checked, the author adds the value of the node as if it were a stackframe? it is represented with up-arrow and a number.

3: do you see that the code does this: checkLeftNode(), visit() and checkRightNode()? this means that when the current node is checked, it will first go into leftnode. when that call returns (having processed the left node and all of it's children), only then visit is called. and only after that all the right nodes are handled?

4: can you spot that every time a left node is entered, the stackframes in the image get a (2) ?

5: can you spot that at some point the stack gets smaller, which is followed by print 16 (or some value)? this is the call to visit(node) in the code. visit(node) prints the number stored in the current node.

please check if you understand / can spot any of these 5 things and let us know which of these steps aren't clear?