I am seeing a lot of tutorials about tree traversals and I am confused by how exactly the in-order algorithm allows us to "climb up" the tree.

For example, in the tree below, I understand that we keep going left until there are no children and then we append the value. But what in the algorithm allows us to "climb back up" to the node of value 2, etc.?

I am struggling to understand this. The algorithm in Python, which I am seeing everywhere, is this:

def printInorder(root):
    if root:
        # First recur on left child
        printInorder(root.left)
        # then print the data of node
        print(root.val),
        # now recur on right child
        printInorder(root.right)

CodePudding user response：

Well let me explain this a bit from this perspective. You are aware of the fact that once you print the root node, then you need to do the same inorder traversal for the subtree having left child as root and the subtree with right child as the root node.

How do we traverse up? It's simply when we get back to the recursive call. Yes it might feel a bit strange but this is how the function call works, once the called function finishes the control goes to parent function and then it finishes the work and the control goes to parent of that.

Now you asked the question,

what "tells the algorithm" that we visited Node 1 and to no longer go to the left

It actually goes to the left of 1 which is basically not a node anymore. It's just None now the function sees that you have an if statement saying do the work only if root is not None. And that's where this function stops calling further. Once it is done it goes back to the parent of it, which is 1. Now at 1 after printing 1 then we again call to traverse the right child of 1 but again it is None so the same thing happens. And then at node 1 we have done everything that we asked the method to do in the if block. It goes back to node 2 the parent.

This is how it works. This diagram will explain it clearly: