Preorder Binary Tree traversal Recursive method

Question

I was trying to understand implementation of Binary Tree traversal (PreOrder). The non recursive approach was fine, but I am totally lost while trying to understand the recursive approach.

Code :

def preorder_print(self, start, traversal): """Root->Left->Right"""
if start:
    traversal += (str(start.value) + "-")
    traversal = self.preorder_print(start.left, traversal)
    traversal = self.preorder_print(start.right, traversal)
return traversal

Binary Tree

My understanding is while reaching Node 2(8-4-2), left of that node 2 is None. So if start: condition would fail.

Below are my questions.

After node2.left is None, how node2.right is traversed? (because if start: condition fails)
After node1, how the logic moves to node5 which rootNode.right?

My understanding on recursion is poor, kindly help!

The key here is that, by the time if start fails, you're nested three calls deep. You'll return back to the instance that called you. If you add some debug print statements, it may become clear. It would help even more to add a "depth" parameter and pass "depth+1" in the recursive calls. Then you'd see that the fail at "depth=3" just goes back to the call where "depth=2" and continues. — Tim Roberts
– Tim Roberts, Commented May 4, 2021 at 3:52
Hi , I tried your code it works, but I have problem in understanding the logic , i.e Node2 left and right both are None. When left is None, in the recursive call self.preorder_print(None,traversal) would be passed right ? so the condition would fail and the entire loop should terminate right ? — Ragesh Kr
– Ragesh Kr, Commented May 4, 2021 at 5:14
No. There is no loop. It's all linear. When you get to node 2, it adds "2" to the list, it calls preorder_print for the left (which immediately returns), then it calls preorder_print for the right (which immediately returns), then it exits back to the next level up, which was the "4" node. — Tim Roberts
– Tim Roberts, Commented May 4, 2021 at 6:01
Now I got it ! When I imagine it as a function within a function I am able to get a hang of it! Thanks a lot for ur effort Tim ! — Ragesh Kr
– Ragesh Kr, Commented May 5, 2021 at 17:37

Tim Roberts · Accepted Answer · 2021-05-04 04:00:01Z

Watch this, see if this helps:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    def addleft(self,value):
        self.left = Node(value)
    def addright(self,value):
        self.right = Node(value)
    def preorder_print(self, start, traversal='', depth=0): 
        print( " "*depth, start.value if start else "None" )
        if start:
            traversal += (str(start.value) + "-")
            print(' '*depth, "check left")
            traversal = self.preorder_print(start.left, traversal, depth+1)
            print(' '*depth, "check right")
            traversal = self.preorder_print(start.right, traversal, depth+1)
        return traversal

base = Node(8)
base.addleft(4)
base.left.addleft(2)
base.left.addright(1)
base.addright(5)
base.right.addright(6)

print( base.preorder_print( base ) )

Output:

 8
 check left
  4
  check left
   2
   check left
    None
   check right
    None
  check right
   1
   check left
    None
   check right
    None
 check right
  5
  check left
   None
  check right
   6
   check left
    None
   check right
    None
8-4-2-1-5-6-

Collectives™ on Stack Overflow

Preorder Binary Tree traversal Recursive method

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related