A 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.
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 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 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.
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 = Noneself.right = Noneself.value = keydef inOrderTraversal(root):if root:# Traverse the left subtreeinOrderTraversal(root.left)# Visit the root nodeprint(root.value, end=" ")# Traverse the right subtreeinOrderTraversal(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)
In pre-order traversal, we visit the root node first, followed by recursively traversing the left subtree, and then recursively traversing the right subtree.
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 = Noneself.right = Noneself.value = keydef preOrderTraversal(root):if root:# Visit the root nodeprint(root.value, end=" ")# Traverse the left subtree recursivelypreOrderTraversal(root.left)# Traverse the right subtree recursivelypreOrderTraversal(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()
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.
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 = Noneself.right = Noneself.value = keydef postOrderTraversal(root):if root:# Traverse the left subtree recursivelypostOrderTraversal(root.left)# Traverse the right subtree recursivelypostOrderTraversal(root.right)# Visit the root nodeprint(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 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.
Let's look at an example of the breadth-first traversal of the same binary search tree:
from collections import dequeclass TreeNode:def __init__(self, key):self.left = Noneself.right = Noneself.value = keydef level_order_traversal(root):if root is None:return# Create a deque to store the nodes for traversalqueue = deque()# Enqueue root nodequeue.append(root)while queue:# Dequeue front nodenode = queue.popleft()# Print value of the nodeprint(node.value, end=" ")# Enqueue left and right children of the dequeued nodeif 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 traversalprint("Level-order traversal of binary search tree is:")level_order_traversal(root)
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.