BINARY SEARCH TREE TRAVERSALS

Unlike linear data structures (arrays, linked lists, stacks, and queues), which have only one logical way to traverse them, trees can be traversed in several ways. The most common tree traversal methods are Depth-First Search (DFS) traversals, which utilize recursion to visit nodes in a specific order.

Understanding these traversals is crucial for coding interviews and is a core requirement of every Data Structures and Algorithms (DSA) practical file.

The Three Recursive DFS Traversals

The three standard DFS traversals are named based on when the root node is visited relative to its left and right subtrees:

1. 1Preorder Traversal (Root, Left, Right): Visit the root node first, then traverse the left subtree, and finally traverse the right subtree. Used to create copies of a tree.
2. 2Inorder Traversal (Left, Root, Right): Traverse the left subtree, visit the root node, and then traverse the right subtree. Crucially, an inorder traversal of a Binary Search Tree (BST) always prints the keys in sorted, ascending order.
3. 3Postorder Traversal (Left, Right, Root): Traverse the left subtree, then traverse the right subtree, and visit the root node last. Used for deleting nodes or evaluating mathematical expression trees.

Visual Trace Example

Consider a BST built by inserting keys in the order: 50, 30, 70.

• ▸Root is 50. Left child is 30. Right child is 70.
• ▸Preorder Trace: Visit 50 (Root) -> Visit 30 (Left) -> Visit 70 (Right). Result: 50, 30, 70.
• ▸Inorder Trace: Visit 30 (Left) -> Visit 50 (Root) -> Visit 70 (Right). Result: 30, 50, 70.
• ▸Postorder Trace: Visit 30 (Left) -> Visit 70 (Right) -> Visit 50 (Root). Result: 30, 70, 50.

C++ Code Implementation

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

void preorder(Node* root) {
    if (!root) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

void postorder(Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

int main() {
    Node* root = nullptr;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);

    cout << "Preorder: "; preorder(root); cout << endl;
    cout << "Inorder: "; inorder(root); cout << endl;
    cout << "Postorder: "; postorder(root); cout << endl;
    return 0;
}

Writing the Lab Report

When compiling your DSA practical report, make sure to detail recursive complexities. The average-case time complexity of BST traversal is O(N) since every node is visited exactly once, and the space complexity is O(H), where H is the height of the tree, representing the recursion stack.

Formatting recursive algorithms and drawing tree diagrams can make writing lab manuals painful. Use Assignment Bot to generate standard, well-organized documentation templates for your tree operations.