Python program to print root to leaf paths without using recursion.
Description:
To print the tree without using recursion we need to iterate it using any order ex- preorder,inorder or postorder,
here I am using preorder to print root to leaf paths.So the idea is to maintain the map to store parent pointers of binary tree nodes.Now whenever we encounter a leaf node while doing iterative preorder traversal, we can easily print root to leaf path using parent pointer.
Program:
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Function to print root to leaf path for a
# leaf using parent nodes stored in map
def printTopToBottomPath(curr, parent):
stk = []
# start from leaf node and keep on appending
# nodes into stack till root node is reached
while (curr):
stk.append(curr)
curr = parent[curr]
# Start popping nodes from stack
# and print them
while len(stk) != 0:
curr = stk[-1]
stk.pop(-1)
print(curr.data, end = " ")
print()
# An iterative function to do preorder
# traversal of binary tree and print
# root to leaf path without using recursion
def printRootToLeaf(root):
# Corner Case
if (root == None):
return
# Create an empty stack and
# append root to it
nodeStack = []
nodeStack.append(root)
# Create a map to store parent
# pointers of binary tree nodes
parent = {}
# parent of root is None
parent[root] = None
# Pop all items one by one. Do following
# for every popped item
# a) append its right child and set its
# parent pointer
# b) append its left child and set its
# parent pointer
# Note that right child is appended first
# so that left is processed first
while len(nodeStack) != 0:
# Pop the top item from stack
current = nodeStack[-1]
nodeStack.pop(-1)
# If leaf node encountered, print
# Top To Bottom path
if (not (current.left) and
not (current.right)):
printTopToBottomPath(current, parent)
# append right & left children of the
# popped node to stack. Also set their
# parent pointer in the map
if (current.right):
parent[current.right] = current
nodeStack.append(current.right)
if (current.left):
parent[current.left] = current
nodeStack.append(current.left)
# Driver Code
if __name__ == '__main__':
# Constructed binary tree is
# 10
# / \
# 8 2
# / \ /
# 3 5 2
root = newNode(10)
root.left = newNode(8)
root.right = newNode(2)
root.left.left = newNode(3)
root.left.right = newNode(5)
root.right.left = newNode(2)
printRootToLeaf(root)
Output:
10 8 3
10 8 5
10 2 2
>>>
Comments