This code is a very confusing way to write a tree traversal but it looks fundamentally correct. Additionally, the output is printed in unusual locations and with misleading labels, so let's rewrite this cleanly before moving on to your questions.
Here's a straightforward way to write an inorder binary tree traversal:
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def inorder(self):
def traverse(node):
if node:
yield from traverse(node.left)
yield node
yield from traverse(node.right)
return traverse(self.root)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/
4 17
/
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
for node in tree.inorder():
print(node.data, end=" ") # => 3 4 6 9 17
The only branch we need is to check whether the root is None--it's best to avoid worrying about the child recursive calls. If they're None, this single branch will handle that condition in the child stack frame.
The above code returns a generator which is more memory-friendly than creating a list and is syntactically simpler.
I'd also keep printing outside of the function. Passing in a callback is a common way to avoid producing a side effect, but using the generator approach above the same outcome is accomplished with a loop, letting us keep the print in the caller.
If you do need to print for debugging purposes, I recommend using whitespace indentation which makes the output into a tree and much easier to follow:
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def inorder(self):
def traverse(node, depth=0):
if node:
yield from traverse(node.left, depth + 1)
yield node, depth
yield from traverse(node.right, depth + 1)
return traverse(self.root)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/
4 17
/
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
for node, depth in tree.inorder():
print(" " * (depth * 2) + str(node.data))
This gives a side-view of the tree:
3
4
6
9
17
With this indentation trick to make it easier to visualize the tree, here's a cleaned-up version of your pre/in/post-order printing which should give a clear picture of the traversal:
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def print_traversals_pedagogical(self):
preorder = []
inorder = []
postorder = []
def traverse(node, depth=0):
if node:
preorder.append(node.data)
print(" " * depth + f"entering {node.data}")
traverse(node.left, depth + 1)
inorder.append(node.data)
print(" " * depth + f"visiting {node.data}")
traverse(node.right, depth + 1)
postorder.append(node.data)
print(" " * depth + f"exiting {node.data}")
traverse(self.root)
print("
preorder ", preorder)
print("inorder ", inorder)
print("postorder", postorder)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/
4 17
/
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
tree.print_traversals_pedagogical()
Output:
entering 9
entering 4
entering 3
visiting 3
exiting 3
visiting 4
entering 6
visiting 6
exiting 6
exiting 4
visiting 9
entering 17
visiting 17
exiting 17
exiting 9
preorder [9, 4, 3, 6, 17]
inorder [3, 4, 6, 9, 17]
postorder [3, 6, 4, 17, 9]
Now we can connect the above output with your code and clear up some of the confusion.
First of all, let's translate your output labels to match the ones shown above:
restart does the same thing as b4 app so you should ignore it to avoid confusion. The if node is not None: print("b4 app", node.data) is always true--we guarantee in the caller that node will not be None.b4 app -> entering (or pushing a new call onto the stack).aft app -> visiting (inorder). Once again, if node is not None: is guaranteed true and should be removed. The parent call checks this and even if they didn't, the program would crash on the line above which uses node.data.inside right is confusing--it's an inorder print but only for nodes that have a right child. I'm not sure what value this adds so I'd ignore it.
Note that you have no exiting (popping a call stack frame/postorder) print statement.
With this context, let's answer your questions:
This is the last time where the code calls itself again before it ends (as far as I can see?).
Yes, this node is about to be exited. To be clear, the function calls itself because it's recursive, but there's only exactly one call per node in the tree.
If this if statement is skipped -- last time the io function is called -- how does the recursion continue?
The call stack pops and execution continues where it left off in the parent. It's not the last time io was called because the parent can (and its parents or its parents' children) can (and do) spawn other calls.
So how was the io function called again and why is node=4 the input?
It wasn't called again--the call frame for node=4 was paused waiting for its children to resolve and when control returned to it, it continued where it left off.
Let's relate my output to your output:
visiting 3 # this is your `aft app 3 True [0]`
exiting 3 # you don't have this print for leaving the node
visiting 4 # this is your `aft app 4 False #[2]`
You can see we exited the call frame for node=3. At that point, node=4 had completed traversing all of its left descendants (there is only one) and then visited its own value inorder before continuing with its right child.
Try playing with different tree structures in the above code and compare the printed debug/pedagogical traversal to your understanding.
