binary tree traversals Algorithm
The binary tree traversals algorithm refers to the method used to access and visit the elements of a binary tree, which is a tree data structure in which each node has at most two children (left and right). There are three common types of traversals: inorder, preorder, and postorder. These traversals are often used for various operations on a binary tree, such as searching for a specific value, printing out the elements, or for copying or deleting the tree. The traversal algorithms are typically implemented using recursion or iteration, depending on the programmer's preference and specific use case.
In inorder traversal, the algorithm first visits the left subtree, then the current node, and finally the right subtree. This traversal is particularly useful for producing a sorted sequence of values from a binary search tree. Preorder traversal, on the other hand, visits the current node first, then the left subtree, and finally the right subtree. This traversal can be used to create a copy of the tree or to produce a prefix expression of a binary expression tree. Lastly, postorder traversal visits the left subtree, then the right subtree, and finally the current node. This type of traversal is often used for deleting the tree or for evaluating a binary expression tree in postfix notation. Each of these traversal methods can be adapted for specific purposes, making binary tree traversals a versatile and essential algorithm in computer science.
# flake8: noqa
"""
This is pure Python implementation of tree traversal algorithms
"""
import queue
from typing import List
class TreeNode:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
def build_tree():
print("\n********Press N to stop entering at any point of time********\n")
check = input("Enter the value of the root node: ").strip().lower() or "n"
if check == "n":
return None
q: queue.Queue = queue.Queue()
tree_node = TreeNode(int(check))
q.put(tree_node)
while not q.empty():
node_found = q.get()
msg = "Enter the left node of %s: " % node_found.data
check = input(msg).strip().lower() or "n"
if check == "n":
return tree_node
left_node = TreeNode(int(check))
node_found.left = left_node
q.put(left_node)
msg = "Enter the right node of %s: " % node_found.data
check = input(msg).strip().lower() or "n"
if check == "n":
return tree_node
right_node = TreeNode(int(check))
node_found.right = right_node
q.put(right_node)
def pre_order(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> pre_order(root)
1 2 4 5 3 6 7
"""
if not isinstance(node, TreeNode) or not node:
return
print(node.data, end=" ")
pre_order(node.left)
pre_order(node.right)
def in_order(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> in_order(root)
4 2 5 1 6 3 7
"""
if not isinstance(node, TreeNode) or not node:
return
in_order(node.left)
print(node.data, end=" ")
in_order(node.right)
def post_order(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> post_order(root)
4 5 2 6 7 3 1
"""
if not isinstance(node, TreeNode) or not node:
return
post_order(node.left)
post_order(node.right)
print(node.data, end=" ")
def level_order(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> level_order(root)
1 2 3 4 5 6 7
"""
if not isinstance(node, TreeNode) or not node:
return
q: queue.Queue = queue.Queue()
q.put(node)
while not q.empty():
node_dequeued = q.get()
print(node_dequeued.data, end=" ")
if node_dequeued.left:
q.put(node_dequeued.left)
if node_dequeued.right:
q.put(node_dequeued.right)
def level_order_actual(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> level_order_actual(root)
1
2 3
4 5 6 7
"""
if not isinstance(node, TreeNode) or not node:
return
q: queue.Queue = queue.Queue()
q.put(node)
while not q.empty():
list = []
while not q.empty():
node_dequeued = q.get()
print(node_dequeued.data, end=" ")
if node_dequeued.left:
list.append(node_dequeued.left)
if node_dequeued.right:
list.append(node_dequeued.right)
print()
for node in list:
q.put(node)
# iteration version
def pre_order_iter(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> pre_order_iter(root)
1 2 4 5 3 6 7
"""
if not isinstance(node, TreeNode) or not node:
return
stack: List[TreeNode] = []
n = node
while n or stack:
while n: # start from root node, find its left child
print(n.data, end=" ")
stack.append(n)
n = n.left
# end of while means current node doesn't have left child
n = stack.pop()
# start to traverse its right child
n = n.right
def in_order_iter(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> in_order_iter(root)
4 2 5 1 6 3 7
"""
if not isinstance(node, TreeNode) or not node:
return
stack: List[TreeNode] = []
n = node
while n or stack:
while n:
stack.append(n)
n = n.left
n = stack.pop()
print(n.data, end=" ")
n = n.right
def post_order_iter(node: TreeNode) -> None:
"""
>>> root = TreeNode(1)
>>> tree_node2 = TreeNode(2)
>>> tree_node3 = TreeNode(3)
>>> tree_node4 = TreeNode(4)
>>> tree_node5 = TreeNode(5)
>>> tree_node6 = TreeNode(6)
>>> tree_node7 = TreeNode(7)
>>> root.left, root.right = tree_node2, tree_node3
>>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
>>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
>>> post_order_iter(root)
4 5 2 6 7 3 1
"""
if not isinstance(node, TreeNode) or not node:
return
stack1, stack2 = [], []
n = node
stack1.append(n)
while stack1: # to find the reversed order of post order, store it in stack2
n = stack1.pop()
if n.left:
stack1.append(n.left)
if n.right:
stack1.append(n.right)
stack2.append(n)
while stack2: # pop up from stack2 will be the post order
print(stack2.pop().data, end=" ")
def prompt(s: str = "", width=50, char="*") -> str:
if not s:
return "\n" + width * char
left, extra = divmod(width - len(s) - 2, 2)
return f"{left * char} {s} {(left + extra) * char}"
if __name__ == "__main__":
import doctest
doctest.testmod()
print(prompt("Binary Tree Traversals"))
node = build_tree()
print(prompt("Pre Order Traversal"))
pre_order(node)
print(prompt() + "\n")
print(prompt("In Order Traversal"))
in_order(node)
print(prompt() + "\n")
print(prompt("Post Order Traversal"))
post_order(node)
print(prompt() + "\n")
print(prompt("Level Order Traversal"))
level_order(node)
print(prompt() + "\n")
print(prompt("Actual Level Order Traversal"))
level_order_actual(node)
print("*" * 50 + "\n")
print(prompt("Pre Order Traversal - Iteration Version"))
pre_order_iter(node)
print(prompt() + "\n")
print(prompt("In Order Traversal - Iteration Version"))
in_order_iter(node)
print(prompt() + "\n")
print(prompt("Post Order Traversal - Iteration Version"))
post_order_iter(node)
print(prompt())
