How to traverse a binary search tree in Python?

Question

Jayant Kumar · Accepted Answer

In Python, you can traverse a binary search tree (BST) using various traversal techniques, including inorder, preorder, and postorder traversals. Each traversal method visits the nodes of the tree in a specific order. Here's how you can implement these traversal methods in Python:
Assuming we have the following Node and BinarySearchTree classes from a previous example:
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BinarySearchTree:
    # ...

def inorder_traversal(self):
        self._inorder_recursive(self.root)

def _inorder_recursive(self, node):
        if node is not None:
            self._inorder_recursive(node.left)
            print(node.key, end=" ")
            self._inorder_recursive(node.right)

def preorder_traversal(self):
        self._preorder_recursive(self.root)

def _preorder_recursive(self, node):
        if node is not None:
            print(node.key, end=" ")
            self._preorder_recursive(node.left)
            self._preorder_recursive(node.right)

def postorder_traversal(self):
        self._postorder_recursive(self.root)

def _postorder_recursive(self, node):
        if node is not None:
            self._postorder_recursive(node.left)
            self._postorder_recursive(node.right)
            print(node.key, end=" ")

In the BinarySearchTree class, we have added three traversal methods: inorder_traversal(), preorder_traversal(), and postorder_traversal(). Each method calls its corresponding recursive helper method _inorder_recursive(), _preorder_recursive(), and _postorder_recursive().

Inorder Traversal: Visits the nodes of the BST in ascending order (left subtree, current node, right subtree).
Preorder Traversal: Visits the nodes of the BST in a top-down fashion (current node, left subtree, right subtree).
Postorder Traversal: Visits the nodes of the BST in a bottom-up fashion (left subtree, right subtree, current node).

Here's an example of using the traversal methods:
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

bst.inorder_traversal()     # Output: 20 30 40 50 60 70 80
print()
bst.preorder_traversal()    # Output: 50 30 20 40 70 60 80
print()
bst.postorder_traversal()   # Output: 20 40 30 60 80 70 50
print()

This example demonstrates how to perform inorder, preorder, and postorder traversals on a binary search tree. Traversing a binary search tree allows you to visit all the nodes in a specific order and perform operations on them.

How to traverse a binary search tree in Python?

Similar Questions

How to traverse a binary search tree in Python?

Jayant Kumar @jayantkumar314

Similar Questions