How does this code work? I don't understand the sequence of logic

Question

#printing nodes via pre-order
def Pre(self, tree):
    if tree != None:
        print(tree.data)
        self.Pre(tree.left)
        self.Pre(tree.right)

Answer 1

This is called 'recursion'.

Assume the tree has the following structure where the left branch (left) is shown as / and the right branch (right) is shown as \

        a
      /   \
      b
     / \
    c   d

When Pre(a) is called, it first checks against None, which is false, thus it goes into the if. It prints the data (.data above) of the current node, then it calls self.Pre(a.left), which is self.Pre(b). Calling self.Pre(b) results in printing b.data and the calling of self.Pre(b.left) which is self.Pre(c) and calling self.Pre(b.right), which is self.Pre(d). This is not done simulatenously but first the left part, then the right part. When both functions have ended, Pre(a.right) is called, and since this is nil, the if will not be called.

The order of calling is:

• Pre(a)
• Pre(b)
• Pre(c)
• 'Pre(d)
• 'Pre(nil)(called froma.right`)

Recursive functions are typically used for nested structures like lists, dictionaries or trees (like in the example above).