Binary Tree Traversal Using Recursion Explanation (python)

Question

I am currently studying Binary trees. I came across this very efficient code for traversing through the tree ( in the example this is an in order traversal ). It uses recursion, which as a concept I understand. However I cannot seem to get my head around how this actually works. The main thing i am confused about is how does it go up the list each time so that start.left isn’t always the same number. Could someone please give a step by step of how this actually traverses up the tree. Thanks in advance

Edited To add clarity to question:

I understand if start is not None, then start.left gets added to the recursion call of the same function.
With each recursion, variable traversal being assigned to the return of the function.
When start is eventually None ( the traversal has completed ) the function returns the traversal element, and continues the process.

Where my confusion is, is that i cannot seem to find where the code, ‘knows’ that its traversed to 4, and now the next element to return is 2. Where is the mechanism, that now stops at 2 and returns it, and so on?

class Node():

def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    
    
def __str__(self):
    return str(self.data)
    

class BinaryTree(object):
def __init__(self, root):
    self.root = Node(root)          
                    
                        
def inorder_print(self, start, traversal):
    """Left -> root -> right"""
    if start:
        traversal = self.inorder_print(start.left, traversal)
        traversal += (str(start.data) + "-")
        traversal = self.inorder_print(start.right, traversal)
        

    return traversal
    
    
    
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3) 
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
tree.root.right.left = Node(6)
tree.root.right.right = Node(7)
tree.root.right.right.right = Node(8)

print(tree.inorder_print(tree.root, ""))

It goes up when it executes `return`. This is quite vague a question. Can you add an explanation step-by-step as far as you can and then pinpoint where exactly in this traversal you don't understand the next step? — trincot, Jan 30 '21 at 17:25
There are plenty of inorder traversals explanations out there. I'd recommend just googling it — sheldonzy, Jan 30 '21 at 17:35
I think you will find [this Q&A](https://stackoverflow.com/a/61165320/633183) helpful, and [this Q&A](https://stackoverflow.com/a/61842976/633183) as well. — Mulan, Jan 30 '21 at 18:48

Samwise · Answer 1 · 2021-01-30T19:58:45.410

One useful tool for understanding the path that an algorithm takes is to add logging to it.

    def inorder_print(self, start, traversal, indent=""):
        """Left -> root -> right"""
        if start:
            print(f"{indent} {start.data} <- '{traversal}'")
            traversal = self.inorder_print(start.left, traversal, indent+" ")
            traversal += (str(start.data) + "-")
            print(f"{indent} {start.data} -- '{traversal}'")
            traversal = self.inorder_print(start.right, traversal, indent+" ")
            print(f"{indent} {start.data} -> '{traversal}'")

        return traversal

allows us to visualize the tree and the order in which each node is added to the traversal:

 1 <- ''
  2 <- ''
   4 <- ''
   4 -- '4-'
   4 -> '4-'
  2 -- '4-2-'
   5 <- '4-2-'
   5 -- '4-2-5-'
   5 -> '4-2-5-'
  2 -> '4-2-5-'
 1 -- '4-2-5-1-'
  3 <- '4-2-5-1-'
   6 <- '4-2-5-1-'
   6 -- '4-2-5-1-6-'
   6 -> '4-2-5-1-6-'
  3 -- '4-2-5-1-6-3-'
   7 <- '4-2-5-1-6-3-'
   7 -- '4-2-5-1-6-3-7-'
    8 <- '4-2-5-1-6-3-7-'
    8 -- '4-2-5-1-6-3-7-8-'
    8 -> '4-2-5-1-6-3-7-8-'
   7 -> '4-2-5-1-6-3-7-8-'
  3 -> '4-2-5-1-6-3-7-8-'
 1 -> '4-2-5-1-6-3-7-8-'

The indentation shows the depth of the stack. Each individual recursive call has three parts -- the left child, self.data, and the right child.

The code "knows" that 2 goes after 4 because 4 happens at the start of 2's call, and the string '2-' is appended immediately afterward:

  2 <- ''          # start of 2's call.  2 starts by calling 4
   4 <- ''             # start of 4's call
   4 -- '4-'           # 4 appends self.data
   4 -> '4-'           # end of 4's call, returning to 2
  2 -- '4-2-'      # 2 appends self.data to what it got from 4, and calls 5
   5 <- '4-2-'         # start of 5's call
   5 -- '4-2-5-'       # 5 appends self.data
   5 -> '4-2-5-'       # end of 5's call, returning to 2
  2 -> '4-2-5-'    # end of 2's call

score 0 · Accepted Answer · answered Jan 30 '21 at 19:41

Ok, sat with it a little longer and figured it out. Thought id post my thoughts so that this question can be marked as answered.

inorder func is called with root and empty string.
start has value of tree.root, while start has value it keeps recursing at traversal = self.inorder_print(start.left, traversal)
it is to be noted, that each time a recursion happens you go further into the tree. start.data = 1. recursion, start.data = 2 recursion, start.data = 4. due to the fact that 4 does not have a left child. the function can finally return. start.data now = 4 and the next line traveral += str(start.data) + "-") can run, adding to the string. However remember that the function is still 2 recurrsions deep. our start.data is back to 2. as that function has finished executing, 2 gets added to traversal via line traveral += str(start.data) + "-")/ #recursion happens with start.right. start.data now =5 start.right has no value, so the function can return 5. this process continues for the whole tree, until all of the functions that have been executed have been completed. the trick to undertanding (at least for me) is that the when you return to a higher level in recursion, the function starts off where it left and doenst start the function from the beginning.

Binary Tree Traversal Using Recursion Explanation (python)

2 Answers2