PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q6(a)

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

Explain pre-order and in-order tree traversal with example.

Solution

Pre-order Traversal (Root Left Right): In pre-order traversal, each node is visited before its subtrees:

  1. Visit/process the Root node (N).
  2. Recursively traverse the Left subtree (L).
  3. Recursively traverse the Right subtree (R).
void preorder(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

In-order Traversal (Left Root Right): In in-order traversal, the left subtree is visited first, then the root, then the right subtree:

  1. Recursively traverse the Left subtree (L).
  2. Visit/process the Root node (N).
  3. Recursively traverse the Right subtree (R).
void inorder(Node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

For a Binary Search Tree (BST), in-order traversal always produces keys in ascending sorted order.

Worked Example: Consider the binary tree:

        10
       /  \
      5    15
     / \     \
    2   7    20
Answer:

All past exam questions for Data Structure and Algorithms