logic penguin - 7 months ago 42

Python Question

In python 3

`class BinaryTree:`

"""

=== Private Attributes ===

@type _root: object | None

@type _left: BinaryTree | None

@type _right: BinaryTree | None

"""

def __init__(self, root, left, right):

if root is None:

# store an empty BinaryTree

self._root = None

self._left = None

self._right = None

else:

self._root = root

self._left = left

self._right = right

def is_empty(self):

return self._root is None

I know how to traverse this binary tree recursively, but I'm wondering how to do it without recursion

Answer

You can use stack method to do tree traversal without recursion. I am giving example for inorder

```
def inOrder(root):
# Set current to root of binary tree
current = root
s = [] # initialze stack
done = 0
while(not done):
# Reach the left most Node of the current Node
if current is not None:
# Place pointer to a tree node on the stack
# before traversing the node's left subtree
s.append(current)
current = current.left
# BackTrack from the empty subtree and visit the Node
# at the top of the stack; however, if the stack is
# empty you are done
else:
if(len(s) >0 ):
current = s.pop()
print current.data,
# We have visited the node and its left
# subtree. Now, it's right subtree's turn
current = current.right
else:
done = 1
```

For more explanation you can consider https://www.youtube.com/watch?v=xLQKdq0Ffjg&t=755s tutorial

Source (Stackoverflow)