In a inorder traversal of a binary search tree, where in the code does it traverse up?

Question

I see where how it goes down the tree, but don't see how it traverses back up and onto the right side of the root. Can someone explain? This is fully functional inorder traversal code in Python.

def inorder(self):
    if self:
        if self.leftChild:
            self.leftChild.inorder()
        print(str(self.value))
        if self.rightChild:
            self.rightChild.inorder()

Where in this code specifically does it go back in the tree?

Trace a couple of iterations manually. You'll find that a *return from calling the function* "pops" one level back - to where it was called from. That's the Up you're looking for. — Jongware, Aug 06 '16 at 21:44
[Python Tutor](http://www.pythontutor.com/) may help you. It visualizes what the computer is doing step-by-step as it executes the program. — Jomy, Aug 06 '16 at 22:12
Possible duplicate of [Understanding recursion](http://stackoverflow.com/questions/717725/understanding-recursion) — Paul Hankin, Aug 07 '16 at 02:18
All python methods without a return statement implicitly return None. Not that that matters because you seem to need to understand recursion — OneCricketeer, Aug 07 '16 at 06:08

score 1 · Accepted Answer · answered Aug 07 '16 at 06:07

1

Reaching the end of a function is the same thing as executing return which is the same thing as executing return None.

For functions that do not return a meaningful value, it is preferred to let execution reach the end of the function rather than place a superfluous return at the end of the function.

answered Aug 07 '16 at 06:07

Alright, so assuming it reaches the end of the function and returns None, how/where does it run the function again if it isn't being called in the code? – Joel De La Cruz Aug 07 '16 at 06:14
@Joel: It doesn't have to run the function again; it was *already running*. – Aug 07 '16 at 06:14
Can you tel me at what line in the above code does it traverse up? Thank you – Joel De La Cruz Aug 07 '16 at 06:24
1

@Joel: It never traverses up. Execution at a node is paused while it's waiting for the function traversing the left subtree to finish. When that completes, it continues executing. – Aug 07 '16 at 06:27
Thanks man, that's what I was looking for that was very helpful. – Joel De La Cruz Aug 07 '16 at 06:28

In a inorder traversal of a binary search tree, where in the code does it traverse up?

1 Answers1