Can someone explain how the recursion works for an inorder BST traversal?

Question

I realize a code for an inorder traversal would look something like

  if left[x] != NULL
    recurse left
    process
  right[x] !=NULL
    recurse right

I coded everything up, works fine. I then started to think more and have over-thought the process and now am lost in how the recursion actually works. Because I think that all the way left, the recursion would end because both nodes are null.

If I am all the way left and both right and left nodes are NULL, how does the recursive call bring me back up to the parent node to continue the traversal?

Answer 1

Like all recursion*, the call stack contains the control for your operations as the recursive calls start to return - program control is returned to the point where your current_node pointer is set to the parent that you were examining prior to making the recursive calls.

(* All recursion, unless there's tail-call optimization going on, in which case it is just a loop).