了解树遍历中的递归

这个问题可能与此类似，但有细微差别。我想了解当两个递归调用一个在另一个递归调用之下时递归是如何工作的。

考虑以下树遍历以进行预排序。

。[参考：educative.io]

我添加了一些打印语句，以了解每个递归调用的工作方式：

from Node import Node
from BinarySearchTree import BinarySearchTree


def preOrderPrint(node):
    if node is not None:
        print(node.val)
        preOrderPrint(node.leftChild)
        print('Done with left node')
        preOrderPrint(node.rightChild) 
        print('Done with right node')


BST = BinarySearchTree(6)
BST.insert(4)
BST.insert(9)
BST.insert(5)
BST.insert(2)
BST.insert(8)
BST.insert(12)

preOrderPrint(BST.root)

输出如下：

6
4
2
Done with left node
Done with right node
Done with left node
5
Done with left node
Done with right node
Done with right node
Done with left node
9
8
Done with left node
Done with right node
Done with left node
12
Done with left node
Done with right node
Done with right node
Done with right node

这是我的理解和问题：

因此，基本情况是当节点为None时，递归终止。左侧的递归首先发生，并在沿着树的方向打印出该节点。一旦到达2的左节点，它将终止。这在“用左节点完成”的打印状态中显示。

权利的递归接管。最后访问的节点是2，所以它从那里开始。由于2的右子元素为None而终止。这在“用正确的节点完成”的打印语句中显示。

现在，右递归上升到4。问题：为什么代码在打印5而不再次打印2之前打印“用左侧节点完成”？它怎么知道左节点已经完成？您可以从堆栈的角度来解释递归使用的内容吗？或任何其他方式。