How to traverse a binary search tree in Python?

Question

Jayant Kumar · Accepted Answer

Table of Contents
Introduction
Traversing a Binary Search Tree (BST) involves visiting all the nodes in a specific order. This is crucial for tasks such as printing tree elements, performing operations on all nodes, or converting the tree to a list. There are three primary traversal methods: in-order, pre-order, and post-order.
1. Traversal Methods
1.1 In-Order Traversal
In-order traversal visits nodes in the following order: left subtree, root node, and then right subtree. For a BST, this traversal yields the nodes in ascending order.
1.2 Pre-Order Traversal
Pre-order traversal visits nodes in the following order: root node, left subtree, and then right subtree. This is useful for operations that need to process the root before its subtrees.
1.3 Post-Order Traversal
Post-order traversal visits nodes in the following order: left subtree, right subtree, and then root node. This method is helpful for tasks like deleting the tree where children are processed before the parent.
2. Python Implementation
Here’s a Python implementation demonstrating all three traversal methods for a Binary Search Tree.
Binary Search Tree Implementation
class BSTNode:
    def __init__(self, key):
        self.value = key
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

# Insert a node into the BST
    def insert(self, key):
        if self.root is None:
            self.root = BSTNode(key)
        else:
            self._insert_recursive(self.root, key)

def _insert_recursive(self, current, key):
        if key &#x3C; current.value:
            if current.left is None:
                current.left = BSTNode(key)
            else:
                self._insert_recursive(current.left, key)
        else:
            if current.right is None:
                current.right = BSTNode(key)
            else:
                self._insert_recursive(current.right, key)

# In-order traversal
    def in_order_traversal(self, node):
        if node:
            self.in_order_traversal(node.left)
            print(node.value, end=' ')
            self.in_order_traversal(node.right)

# Pre-order traversal
    def pre_order_traversal(self, node):
        if node:
            print(node.value, end=' ')
            self.pre_order_traversal(node.left)
            self.pre_order_traversal(node.right)

# Post-order traversal
    def post_order_traversal(self, node):
        if node:
            self.post_order_traversal(node.left)
            self.post_order_traversal(node.right)
            print(node.value, end=' ')

Example Usage
# Create a Binary Search Tree and insert some nodes
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

# Perform and print different traversals
print("In-order Traversal:")
bst.in_order_traversal(bst.root)  # Output: 20 30 40 50 60 70 80
print("
Pre-order Traversal:")
bst.pre_order_traversal(bst.root)  # Output: 50 30 20 40 70 60 80
print("
Post-order Traversal:")
bst.post_order_traversal(bst.root)  # Output: 20 40 30 60 80 70 50

Conclusion
Traversing a Binary Search Tree (BST) is essential for various operations such as printing elements or performing actions on all nodes. The three primary traversal methods— in-order, pre-order, and post-order—each have unique use cases. By implementing these traversal techniques in Python, you can effectively manage and utilize BSTs for a variety of applications.

How to traverse a binary search tree in Python?

Similar Questions