Tree
Practice Questions
Implementation of Binary Trees
Implementation of Binary tree traversals in python
First we have defined a binary tree from the above code where the elements are 1,2,3,4,5,6,7.
Now let us define print_tree function where it takes value of traversal type with the following conditions.
def print_tree(self, traversal_type):
if traversal_type == "preorder":
return self.preorder_print(tree.root, "")
elif traversal_type == "inorder":
return self.inorder_print(tree.root, "")
elif traversal_type == "postorder":
return self.postorder_print(tree.root, "")
else:
print("Traversal type " + str(traversal_type) + " is not supported.")
return False
Here the function is pre defined to taking another function for the values of preorder,inorder,post order and else.
Next let us define preorder function and also assign traversal values accordingly.
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
print(tree.print_tree("preorder"))
The above code gives 1-2-4-5-3-6-7- as output as we can see that tree is passing in the preorder path.
1
/ \
2 3
/ \ / \
4 5 6 7 it
Next let us define in-order function and also assign traversal values accordingly.
def inorder_print(self, start, traversal):
"""Left->Root->Right"""
if start:
traversal = self.inorder_print(start.left, traversal)
traversal += (str(start.value) + "-")
traversal = self.inorder_print(start.right, traversal)
return traversal
print(tree.print_tree("inorder"))
The above code gives 4-2-5-1-6-3-7-as output as we can see that tree is passing in the In-order path.
1
/ \
2 3
/ \ / \
4 5 6 7
Next let us define post-order function and also assign traversal values accordingly.
def postorder_print(self, start, traversal):
"""Left->Right->Root"""
if start:
traversal = self.postorder_print(start.left, traversal)
traversal = self.postorder_print(start.right, traversal)
traversal += (str(start.value) + "-")
return traversal
print(tree.print_tree("postorder"))
The above code gives 4-5-2-6-7-3-1- as output as we can see that tree is passing in the In-order path.
1
/ \
2 3
/ \ / \
4 5 6 7
Thus binary tree can be traversed as above.
Try here>>>