Past exam question: 2078 Chaitra (Regular), Q6(a)
Open in the Padhaiko appQuestion
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:
- Visit/process the Root node (
N). - Recursively traverse the Left subtree (
L). - 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:
- Recursively traverse the Left subtree (
L). - Visit/process the Root node (
N). - 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
- Pre-order (
N-L-R): Visit10, traverse left (5, 2, 7), traverse right (15, 20)10, 5, 2, 7, 15, 20. - In-order (
L-N-R): Traverse left (2, 5, 7), visit10, traverse right (15, 20)2, 5, 7, 10, 15, 20.
Answer:
- Pre-order (
Root-Left-Right): Processes root before subtrees; on the example tree gives10, 5, 2, 7, 15, 20. - In-order (
Left-Root-Right): Processes left subtree, root, then right subtree (yielding sorted order on a BST); on the example tree gives2, 5, 7, 10, 15, 20.