Traversal in Binary Search Tree (BST)
Traversal is the process of visiting each node in a BST systematically to perform
some operations like printing node values, searching, or modifying data.
Traversing a tree is crucial because it ensures that every node is visited, often in a
specific order.
There are three main types of traversal methods in BST: Inorder, Preorder, and
Postorder. Each method has a specific way of visiting nodes, and they serve
different purposes.
1. Inorder Traversal (Left, Root, Right)
Order:
Visit the left subtree first, then the root node, and finally the right subtree.
Steps:
1. Start at the root.
2. Go to the leftmost node in the left subtree.
3. Visit the root of the current subtree.
4. Go to the right subtree and repeat.
Use Case:
Inorder traversal outputs the node values in ascending order if the tree is a
BST.
Example:
For this tree:
markdown
Copy code
5
/ \
3 7
/ \
2 4
Inorder Output: 2, 3, 4, 5, 7.
C++ Code:
cpp
Copy code
void inorderTraversal(Node* root) {
if (root != nullptr) {
inorderTraversal(root->left); // Visit left subtree
cout << root->value << " "; // Visit root
inorderTraversal(root->right); // Visit right subtree
}
}
2. Preorder Traversal (Root, Left, Right)
Order:
Visit the root node first, then the left subtree, and finally the right subtree.
Steps:
1. Visit the root.
2. Go to the left subtree and visit all nodes in Preorder.
3. Go to the right subtree and do the same.
Use Case:
Preorder traversal is useful for creating a copy of the tree or exporting the
tree structure to a file.
Example:
For this tree:
markdown
Copy code
5
/ \
3 7
/ \
2 4
Preorder Output: 5, 3, 2, 4, 7.
C++ Code:
cpp
Copy code
void preorderTraversal(Node* root) {
if (root != nullptr) {
cout << root->value << " "; // Visit root
preorderTraversal(root->left); // Visit left subtree
preorderTraversal(root->right); // Visit right subtree
}
}
3. Postorder Traversal (Left, Right, Root)
Order:
Visit the left subtree first, then the right subtree, and finally the root node.
Steps:
1. Go to the left subtree and visit all nodes in Postorder.
2. Go to the right subtree and do the same.
3. Visit the root node.
Use Case:
Postorder traversal is useful for deleting the tree (e.g., when freeing
memory in programs).
Example:
For this tree:
markdown
Copy code
5
/ \
3 7
/ \
2 4
Postorder Output: 2, 4, 3, 7, 5.
C++ Code:
cpp
Copy code
void postorderTraversal(Node* root) {
if (root != nullptr) {
postorderTraversal(root->left); // Visit left subtree
postorderTraversal(root->right); // Visit right subtree
cout << root->value << " "; // Visit root
}
}
Other Types of Traversal
1. Level-Order Traversal (Breadth-First Search)
o Visit nodes level by level, starting from the root, then moving to the
next level, and so on.
o Requires a queue for implementation.
Use Case: Useful in finding the shortest path in an unweighted tree or for
printing a tree level by level.
Example Output for the above tree: 5, 3, 7, 2, 4.
C++ Code:
cpp
Copy code
void levelOrderTraversal(Node* root) {
if (root == nullptr) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
cout << current->value << " ";
if (current->left != nullptr) q.push(current->left);
if (current->right != nullptr) q.push(current->right);
}
}
Summary of Traversals
Traversal
Order Use Case
Type
Left → Root → Sorting values, outputting data in ascending
Inorder
Right order.
Root → Left →
Preorder Exporting tree structure or creating a copy.
Right
Left → Right → Deleting a tree or evaluating mathematical
Postorder
Root expressions.
Shortest path or printing level-by-level
Level-Order Level by level
structure.
By understanding these traversal methods, you can use BSTs effectively for
different purposes, whether you’re sorting data, creating backups, or evaluating
mathematical trees.
