In-order binary tree traversal is a technique used to visit all the nodes of a binary tree in the following order: First, all the nodes in the left subtree are visited in in-order fashion, then the root node of the current tree is visited, and finally all the nodes in the right subtree are visited in in-order fashion. The animated examples discussed in the next section will make the definition more clear.
Animation of In-Order Binary Tree Traversal
Let’s consider the below binary tree and apply the in-order tree traversal technique:
Node A is the root node of the binary tree. Before we can visit this node, we need to visit all nodes under it’s left subtree. Visited nodes will be colored in green.
So first we visit all the nodes under the left subtree of node A i.e., subtree with root as node B in in-order fashion. We apply the same logic again i.e, visit all nodes in left subtree under node B, then visit node B, and then visit all nodes in right subtree under node B.
Left subtree of node B contains a singe node D, so we just visit that node, then visit node B and finally visit node E.
Now that all the nodes under the left subtree of node A are visited, we can now visit node A.
Now we need to visit all nodes under the right subtree of node A in in-order fashion.
This is the order in which we visited all the nodes: D, B, E, A, F, C, G.
If you do an in-order traversal on a binary search tree like the one shown below, the order of elements in in-order traversal will be in ascending order (10, 20, 30, 50, 60, 70, 80):
Recursive Implementation
Below is the implementation of a function which takes in the root node of a binary tree and traverses all the nodes in In-Order fashion. It uses recursion technique which is much simpler and straightforward than the iterative version.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def in_order_traversal(node):
# Base case: if the node is None, return
if node is None:
return
# Step 1: Traverse the left subtree recursively
in_order_traversal(node.left)
# Step 2: Visit the current node
# print its value or perform any other operation
print(node.value, end=" ")
# Step 3: Traverse the right subtree recursively
in_order_traversal(node.right)
# Create a sample binary tree
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# In-order traversal usage
if __name__ == "__main__":
tree_root = create_binary_tree()
print("In-Order Traversal:")
in_order_traversal(tree_root)
Iterative Implementation
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def iterative_in_order_traversal(root):
if root is None:
return
stack = []
current = root
while stack or current:
# Traverse to the leftmost node
while current:
stack.append(current)
current = current.left
# Visit the node at the top of the stack
current = stack.pop()
# Print the node or perform any operation on it
print(current.value, end=" ")
# Move to the right subtree
current = current.right
# Create a sample binary tree
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Iterative in-order traversal usage
if __name__ == "__main__":
tree_root = create_binary_tree()
print("Iterative In-Order Traversal:")
iterative_in_order_traversal(tree_root)
Applications/Use Cases
- Sorting: In-order traversal on a Binary Search Tree results in elements being visited in sorted order. This property makes it an efficient way to traverse through all elements in a binary search tree in sorted order.
- Expression Evaluation:: In arithmetic expression trees, in-order traversal helps in computing the result or converting the tree back to its original infix/prefix or postfix expression.