Core Concept Mastery • DSA Module
Tree traversal is the process of visiting every node in a tree exactly once. Unlike arrays where you visit elements sequentially, trees offer multiple traversal orders: Preorder (Root-Left-Right), Inorder (Left-Root-Right), and Postorder (Left-Right-Root).
Preorder: Like reading a book — you read the chapter title (Root) first, then the left section, then the right section. Inorder: Like reading a math expression — you read left operand, then operator (Root), then right operand. Postorder: Like cleaning up — you clean left room, then right room, then the main room (Root) last.
Unlike arrays (0 to n), trees have multiple ways to walk through them.
Root First
Root → Left → Right
Use: Copying trees
Root Middle
Left → Root → Right
Use: BST = Sorted
Root Last
Left → Right → Root
Use: Deleting trees
1void preorder(struct Node* root) {2if (root == NULL) return;3printf("%d ", root->data); // Process Root FIRST5preorder(root->left); // Then Left6preorder(root->right); // Then Right7}
Inorder traversal of a BST always gives elements in sorted (ascending) order!
PREorder = Process Root Early (before children)
INorder = Process Root In the middle (between children)
POSTorder = Process Root Last (after children)
Walking Through a Tree
Why Multiple Ways?
Unlike arrays where you go from index 0 to n-1 sequentially, trees branch. You can visit nodes in different orders, each serving different purposes.
The Three Standard Traversals
1. Preorder (Root-Left-Right)
Visit order: Root → Left subtree → Right subtree
2. Inorder (Left-Root-Right)
Visit order: Left subtree → Root → Right subtree
3. Postorder (Left-Right-Root)
Visit order: Left subtree → Right subtree → Root
How to Remember
Think of when you visit the Root:
Recursive Implementation
All three traversals follow the same pattern:
1. If tree is empty (NULL), return
2. Recursively traverse left subtree
3. Recursively traverse right subtree
4. Process current node
The only difference is WHEN you process the current node:
Time Complexity
All traversals visit every node exactly once: O(n) where n is the number of nodes.
Space Complexity
Depends on tree height: O(h) where h is height. For balanced tree: O(log n). For skewed tree: O(n).
Special Property: Inorder + BST
Inorder traversal of a Binary Search Tree always gives elements in sorted (ascending) order. This is because Left < Root < Right property ensures smaller elements come before larger ones.
Traversals are fundamental to tree operations. You need traversals to print tree contents, copy trees, delete trees, evaluate expressions, serialize data, and search for elements. Different traversal orders serve different purposes — Inorder gives sorted order for BSTs, Postorder is used for deletion, Preorder for copying.
"What is the order of node visitation in an Inorder traversal?"
Inorder traversal visits nodes in Left-Root-Right order. For each node, you first recursively visit the left subtree, then process the current node, then recursively visit the right subtree. For a BST, this gives elements in sorted order.