Binary trees are fundamental data structures in computer science, and traversing them efficiently is a crucial skill for any programmer. In this blog post, we’ll explore the three main traversal techniques—preorder, inorder, and postorder—and learn how to implement them in Python. We’ll also cover how to reconstruct a binary tree from traversal sequences and visualize the results.
Understanding Binary Tree Traversals
A binary tree consists of nodes, where each node can have at most two children: a left child and a right child. Traversal refers to the process of visiting each node exactly once in a specific order. The three primary traversal methods are defined by the order in which we visit the root node relative to its children:
- Preorder Traversal: Visit the root node first, then recursively traverse the left subtree, followed by the right subtree. (Root → Left → Right)
- Inorder Traversal: Recursively traverse the left subtree first, then visit the root node, followed by the right subtree. (Left → Root → Right)
- Postorder Traversal: Recursively traverse the left subtree first, then the right subtree, and finally visit the root node. (Left → Right → Root)
Implementing Preorder Traversal
Let’s start with preorder traversal. We’ll create a function to build a binary tree from a preorder sequence (using ‘None’ to represent null nodes) and another function to visualize the tree.
import matplotlib.pyplot as plt
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_tree_from_preorder(preorder):
if not preorder:
return None
root_value = preorder.pop(0)
if root_value is None:
return None
root = Node(root_value)
root.left = build_tree_from_preorder(preorder)
root.right = build_tree_from_preorder(preorder)
return root
def plot_tree(node, x, y, dx, dy, ax):
if node:
ax.text(x, y, str(node.value), style='italic', bbox={'facecolor': 'red', 'alpha': 0.5, 'pad': 10})
if node.left:
ax.plot([x, x - dx], [y, y - dy], 'k-')
if __name__ == "__main__":
main_preorder()Example 1: Right-skewed Tree
Input:
Enter preorder traversal (space-separated, use 'None' for null nodes): 1 None 2 None 3 None 4Output:
Preorder Traversal: [1, None, 2, None, 3, None, 4]The resulting tree structure:
1
\
2
\
3
\
4Example 2: Balanced Tree
Input:
Enter preorder traversal (space-separated, use 'None' for null nodes): 1 2 None None 3 4 None None 5 None NoneOutput:
Preorder Traversal: [1, 2, None, None, 3, 4, None, None, 5, None, None]The resulting tree structure:
1
/ \
2 3
/ \
4 5Implementing Inorder Traversal
Inorder traversal is particularly useful for binary search trees (BSTs) because it visits nodes in ascending order. Here’s how to build a balanced binary tree from an inorder sequence:
import matplotlib.pyplot as plt
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_balanced_tree_from_inorder(inorder):
"""Build a balanced binary tree from an inorder traversal array"""
if not inorder:
return None
mid = len(inorder) // 2
root = Node(inorder[mid])
root.left = build_balanced_tree_from_inorder(inorder[:mid])
root.right = build_balanced_tree_from_inorder(inorder[mid+1:])
return root
def inorder_traversal(root):
"""Inorder traversal (for verification)"""
if not root:
return []
if __name__ == "__main__":
main_inorder()Example Input:
Enter inorder traversal (space-separated): 4 2 5 1 6 3 7Converting Between Traversal Sequences
One interesting problem is reconstructing a binary tree (and thus deriving the third traversal) from two given traversal sequences. Let’s explore some common conversions.
From Preorder and Postorder to Inorder
Note: A binary tree cannot be uniquely determined from preorder and postorder traversals alone. We’ll assume a full binary tree (each node has 0 or 2 children) for this implementation.
import matplotlib.pyplot as plt
# Node class remains the same
def build_tree_from_preorder_postorder(preorder, postorder):
if not preorder or not postorder:
return None
root_value = preorder[0]
root = Node(root_value)
if len(preorder) == 1:
return root
left_root_value = preorder[1]
left_root_idx = postorder.index(left_root_value)
root.left = build_tree_from_preorder_postorder(preorder[1:left_root_idx+2], postorder[:left_root_idx+1])
root.right = build_tree_from_preorder_postorder(preorder[left_root_idx+2:], postorder[left_root_idx+1:-1])
return root
# inorder_traversal and plot_tree functions remain the same
def main_pre_to_in():
preorder_input = input("Enter preorder traversal (space-separated): ")
if __name__ == "__main__":
main_pre_to_in()Input:
Enter preorder traversal (space-separated): 1 2 4 5 3 6 7Enter postorder traversal (space-separated): 4 5 2 6 7 3 1Output:
Inorder traversal: [4, 2, 5, 1, 6, 3, 7]From Inorder and Postorder to Preorder
import matplotlib.pyplot as plt
# Node class remains the same
def build_tree_from_inorder_postorder(inorder, postorder):
if not inorder or not postorder:
return None
root_value = postorder[-1]
root = Node(root_value)
mid_idx = inorder.index(root_value)
root.left = build_tree_from_inorder_postorder(inorder[:mid_idx], postorder[:mid_idx])
root.right = build_tree_from_inorder_postorder(inorder[mid_idx+1:], postorder[mid_idx:-1])
return root
def preorder_traversal(root):
if not root:
return []
return [root.value] + preorder_traversal(root.left) + preorder_traversal(root.right)
# plot_tree function remains the same
if __name__ == "__main__":
main_in_post_to_pre()From Inorder and Preorder to Postorder
import matplotlib.pyplot as plt
# Node class remains the same
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_value = preorder[0]
root = Node(root_value)
mid_idx = inorder.index(root_value)
root.left = build_tree(preorder[1:mid_idx+1], inorder[:mid_idx])
root.right = build_tree(preorder[mid_idx+1:], inorder[mid_idx+1:])
return root
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value]
# plot_tree function remains the same
def main_in_pre_to_post():
if __name__ == "__main__":
main_in_pre_to_post()Conclusion
Understanding binary tree traversals is essential for many algorithms and applications, from expression parsing to database indexing. The ability to convert between different traversal sequences demonstrates a deep understanding of tree structures.
In this post, we’ve covered:
- The three main traversal techniques (preorder, inorder, postorder)
- Implementing traversals in Python
- Visualizing binary trees
- Converting between traversal sequences
Practice with different tree structures to reinforce your understanding. You might also want to explore iterative implementations of these traversals, which use stacks instead of recursion.
