Binary Search Tree traverse method, what makes it go up from lowest left child(leaf)?

Question

I have a hard time understanding how the SearchTree "traverse in order method" goes up after it reaches the most left leaf. I UNDERSTAND that at first root becomes leftchild, than down 1 level leftchild again, again, until it becomes the lowest left leaf, which has no left child and no right child. OK. But how does it go level up after the root is the last leaf. What is the EXACT line of code that makes the traverse method go one level up from the lowest left child. Since for that node both root.leftchild and root.rightchild are null. This is magic to me.

public void inOrderTraverseTree(Node root) {

        if (root != null) {

            inOrderTraverseTree(root.leftChild);

            System.out.println(root);

            inOrderTraverseTree(root.rightChild);

        }

}

Answer 1

Imagine you've a stack, and every call to inOrderTraverseTree(Node root) being stored in the stack through some pointer(if you don't know what a pointer is, imagine there's a variable that represents a function call).

So, if inOrderTraverseTree(Node root) is called n times, the stack will have n pointers to the function.

What you're asking is, what'll happen after n calls? Well, the answer is, we return to the function that was previously called. This is done by removing the pointer at the top of the stack. Now, what we'll have at the top of the stack is the pointer to the previous function call.

In short, every time a recursive call is made, a pointer to the function is pushed to the stack. Once we reach the end of traversal, we start the popping elements from the stack one-by-one.

Since this operation involves push & pop only, this is the very reason a stack is being to store function calls.

Answer 2

This is because of the property of the recursive function which returns to it parent calling function after getting executed. e.g.
20
/ \
10 30

this is a tree with its root as 20. Now walking through the inOrderTraverseTree code of yours: 1. call inOrderTraverseTree(20) 2. check for root being null, here 20 is not null. 3. call inOrderTraverseTree(10) {left of 20 is 10} 4. check for root being null, here 10 is not null. 5. call inOrderTraverseTree(null) {left of 10 is null} 6. check for root being null, here it is null.Hence exit out of "if",return to calling function,i.e step 4{root=10} 7. print root,i.e print 10. 8. call inOrderTraverseTree(null) {right of 10 is null} 9. check for root being null, here it is null.Hence exit out of "if",return to calling function,i.e step 3{root=20}.{complete execution for root=10 is completed} 10.print root,i.e print 20. 11.call inOrderTraverseTree(30){right of 20 is 30} 12.check for root being null, here 30 is not null. 13.call inOrderTraverseTree(null){left of 30 is null} 14. check for root being null, here it is null.Hence exit out of "if",return to calling function,i.e step 12{root=30} 15. print root,i.e print 30. 16. call inOrderTraverseTree(null) {right of 30 is null} 17. check for root being null, here it is null.Hence exit out of "if",return to calling function,i.e step 11{root=20}.{complete execution for root=30 is completed}

with this the complete execution of inOrderTraverseTree call with root 20 is also completed and the value printed is 10 (in step 7), 20 (in step 10), 30 (in step 15): 10 20 30. Now coming to "code that makes the traverse method go one level up from the lowest left child" : you can see this happening in step 9. Where the leftmost child is returned to its parent calling function when the complete function cycle for leftmost child is fully executed. This is the main property of recursive function.