Methods of traversing a binary search tree

Binary Search Tree (BST) is a binary tree where each node has a key and a value. It allows addition, removal, and fast lookup of items stored in it. The nodes in a BST are arranged based on the following:

  • Nodes in the left subtree of a node will contain keys smaller than the key of that node.

  • Nodes in the right subtree of a node will contain keys greater than the key of that node.

  • The left and right subtrees of any node will also be binary search trees.

Binary seach tree
Binary seach tree

There are many ways to traverse a binary search tree, which essentially means visiting each node in the tree and processing/outputting its value.

Depth-first traversal

Depth-first traversal involves traversing the tree by visiting nodes along each branch as deeply as possible before backtracking. There are three main methods of depth-first traversal:

In-order traversal

In in-order traversal, we traverse the left subtree, then visit the root, and traverse the right subtree. In a BST, this results in visiting nodes in ascending order.

1 of 12

Let's look at an example of the in-order traversal of a binary search tree shown above:

class BSTNode:
def __init__(self, key):
self.left = None
self.right = None
self.value = key
def inOrderTraversal(root):
if root:
# Traverse the left subtree
inOrderTraversal(root.left)
# Visit the root node
print(root.value, end=" ")
# Traverse the right subtree
inOrderTraversal(root.right)
if __name__ == "__main__":
root = BSTNode(50)
root.left = BSTNode(40)
root.right = BSTNode(70)
root.left.left = BSTNode(20)
root.left.right = BSTNode(45)
root.right.left = BSTNode(60)
root.right.right = BSTNode(99)
print("Inorder traversal:")
inOrderTraversal(root)

Pre-order traversal

In pre-order traversal, we visit the root node first, followed by recursively traversing the left subtree, and then recursively traversing the right subtree.

1 of 9

Let's look at an example of the pre-order traversal of the same binary search tree:

class BSTNode:
def __init__(self, key):
self.left = None
self.right = None
self.value = key
def preOrderTraversal(root):
if root:
# Visit the root node
print(root.value, end=" ")
# Traverse the left subtree recursively
preOrderTraversal(root.left)
# Traverse the right subtree recursively
preOrderTraversal(root.right)
if __name__ == "__main__":
root = BSTNode(50)
root.left = BSTNode(40)
root.right = BSTNode(70)
root.left.left = BSTNode(20)
root.left.right = BSTNode(45)
root.right.left = BSTNode(60)
root.right.right = BSTNode(99)
print("Preorder traversal:")
preOrderTraversal(root)
print()

Post-order traversal

In post-order traversal, we first recursively traverse the left subtree, then recursively traverse the right subtree, and finally visit the root node. This traversal is generally used to delete nodes in the tree.

1 of 15

Let's look at an example of the post-order traversal of the same binary search tree:

class BSTNode:
def __init__(self, key):
self.left = None
self.right = None
self.value = key
def postOrderTraversal(root):
if root:
# Traverse the left subtree recursively
postOrderTraversal(root.left)
# Traverse the right subtree recursively
postOrderTraversal(root.right)
# Visit the root node
print(root.value, end=" ")
if __name__ == "__main__":
root = BSTNode(50)
root.left = BSTNode(40)
root.right = BSTNode(70)
root.left.left = BSTNode(20)
root.left.right = BSTNode(45)
root.right.left = BSTNode(60)
root.right.right = BSTNode(99)
print("Postorder traversal:")
postOrderTraversal(root)

Breadth-first search

Breadth-first search traversal explores the tree level by level, visiting all the nodes at the present depth before moving on to the nodes at the next depth level.

1 of 9

Let's look at an example of the breadth-first traversal of the same binary search tree:

from collections import deque
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.value = key
def level_order_traversal(root):
if root is None:
return
# Create a deque to store the nodes for traversal
queue = deque()
# Enqueue root node
queue.append(root)
while queue:
# Dequeue front node
node = queue.popleft()
# Print value of the node
print(node.value, end=" ")
# Enqueue left and right children of the dequeued node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if __name__ == "__main__":
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(70)
root.left.left = TreeNode(20)
root.left.right = TreeNode(40)
root.right.left = TreeNode(60)
root.right.right = TreeNode(80)
# Level-order traversal
print("Level-order traversal of binary search tree is:")
level_order_traversal(root)

Conclusion

Depth-first and breadth-first traversals are two major ways to traverse a binary search tree. A breadth-first search traverses the tree level by level, whereas in the depth-first search, we traverse the tree by visiting nodes along each branch as deeply as possible before backtracking. The three main methods of depth-first traversal are in-order, pre-order, and post-order traversal. The main difference between these two approaches lies in the way the tree is traversed.

Copyright ©2024 Educative, Inc. All rights reserved