Tree Traversal Postorder Left Right Root in DSA C - Build from Scratch

Tree Traversal Postorder Left Right Root

📖 Scenario: Imagine you have a family tree, and you want to visit each family member starting from the youngest children, then their parents, and finally the grandparents. This way of visiting is called postorder traversal in trees.

🎯 Goal: You will build a simple binary tree in C and write a function to print its nodes in postorder (left child, right child, then root).

📋 What You'll Learn

Create a binary tree with exactly three nodes: root with value 1, left child with value 2, and right child with value 3

Create a pointer variable to hold the root node

Write a recursive function called postorder that prints nodes in left-right-root order

Print the values of the nodes in postorder traversal separated by spaces

💡 Why This Matters

🌍 Real World

Tree traversals are used in many real-world applications like file system navigation, expression evaluation, and organizing hierarchical data.

💼 Career

Understanding tree traversal is important for software developers working with data structures, databases, and algorithms.

1

Create the binary tree nodes

Create a struct called Node with an int data and two pointers left and right. Then create three nodes: root with data 1, root->left with data 2, and root->right with data 3.

DSA C

# Define struct Node and create root, root->left, root->right nodes
// Your code here

Hint

Remember to set left and right pointers of leaf nodes to NULL.

2

Create a pointer to the root node

Create a pointer variable called tree and set it equal to root.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = (Node*)malloc(sizeof(Node));
    root->left->data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (Node*)malloc(sizeof(Node));
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    Node* tree = NULL;  // Your code here

    return 0;
}

Hint

Just assign tree to root to keep a pointer to the tree.

3

Write the postorder traversal function

Write a recursive function called postorder that takes a Node* called node. It should first call itself on node->left, then on node->right, and finally print node->data followed by a space. Make sure to check if node is NULL before calling recursively or printing.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

void postorder(Node* node) {
    // Your code here
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = (Node*)malloc(sizeof(Node));
    root->left->data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (Node*)malloc(sizeof(Node));
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    Node* tree = root;

    // Call postorder here

    return 0;
}

Hint

Remember the order: left child, right child, then print the current node's data.

4

Print the postorder traversal output

Add a printf statement after calling postorder(tree) to print a newline character '\n' so the output looks clean.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

void postorder(Node* node) {
    if (node == NULL) {
        return;
    }
    postorder(node->left);
    postorder(node->right);
    printf("%d ", node->data);
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = (Node*)malloc(sizeof(Node));
    root->left->data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (Node*)malloc(sizeof(Node));
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    Node* tree = root;

    postorder(tree);

    // Print newline here
    // Your code here

    return 0;
}

Hint

Print a newline character after the postorder traversal to keep output clean.

Practice

1. What is the correct order of nodes visited in a postorder tree traversal?

easy

A. Right subtree, Left subtree, Root node

B. Root node, Left subtree, Right subtree

C. Root node, Right subtree, Left subtree

D. Left subtree, Right subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits the left subtree first, then the right subtree, and finally the root node.

2. Step 2: Apply the order to the traversal

   Following this order ensures all children are visited before the parent node.

3. Final Answer:

   Left subtree, Right subtree, Root node -> Option D

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember: postorder ends with the root node [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Visiting root before children
• Swapping left and right subtree order

2. Which of the following C code snippets correctly implements the postorder traversal function for a binary tree node struct Node?

easy

A. void postorder(struct Node* root) { if(root) { printf("%d ", root->data); postorder(root->left); postorder(root->right); } }

B. void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } }

C. void postorder(struct Node* root) { if(root) { postorder(root->right); postorder(root->left); printf("%d ", root->data); } }

D. void postorder(struct Node* root) { if(root) { postorder(root->left); printf("%d ", root->data); postorder(root->right); } }

Solution

1. Step 1: Check traversal order in code

   Postorder requires visiting left subtree, then right subtree, then root node.

2. Step 2: Match code to postorder steps

   void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } } calls postorder on left, then right, then prints root data, matching postorder.

3. Final Answer:

   Correct postorder traversal code -> Option B

4. Quick Check:

   Left, Right, Root in code = void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } } [OK]

Hint: Print root after left and right recursive calls [OK]

Common Mistakes:

• Printing root before children (preorder)
• Swapping left and right subtree calls
• Missing null check for root

3. Given the binary tree below:

    1
   / \
  2   3
 / \
4   5

What is the output of a postorder traversal?

medium

A. 2 4 5 3 1

B. 1 2 4 5 3

C. 4 5 2 3 1

D. 4 2 5 3 1

Solution

1. Step 1: Traverse left subtree of root (1)

   Left subtree rooted at 2: postorder visits 4, then 5, then 2.

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), then visit root 1 last.

3. Final Answer:

   4 5 2 3 1 -> Option C

4. Quick Check:

   Left, Right, Root = 4 5 2 3 1 [OK]

Hint: Visit children fully before printing parent [OK]

Common Mistakes:

• Printing root too early
• Mixing left and right subtree order
• Confusing preorder or inorder output

4. Consider the following C function for postorder traversal:

void postorder(struct Node* root) {
    if(root == NULL) return;
    postorder(root->right);
    postorder(root->left);
    printf("%d ", root->data);
}

What is the main issue with this code?

medium

A. It visits the right subtree before the left subtree, reversing the correct order

B. It does not check if root is NULL before recursion

C. It prints the root before visiting children

D. It causes infinite recursion

Solution

1. Step 1: Analyze the order of recursive calls

   The code calls postorder on right subtree first, then left subtree, which reverses the expected left-right order.

2. Step 2: Check printing position

   Printing root after children is correct, but subtree order is wrong.

3. Final Answer:

   Visits right subtree before left, reversing order -> Option A

4. Quick Check:

   Left before right needed, code does right before left [OK]

Hint: Left subtree call must come before right subtree call [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Printing root too early
• Missing null check (not in this code though)

5. You have a binary tree where each node stores an integer. You want to collect all node values in postorder traversal into an array. Which approach correctly achieves this?

hard

A. Use recursion: traverse left subtree, traverse right subtree, then append root value to array

B. Use recursion: append root value, then traverse left and right subtrees

C. Use a queue to enqueue root first, then left and right children

D. Traverse the tree level by level and append nodes to array

Solution

1. Step 1: Understand postorder traversal for collection

   Postorder means visiting left subtree, right subtree, then root, so values must be appended in that order.

2. Step 2: Choose correct method to collect values

   Recursion that appends root after children ensures correct postorder sequence in the array.

3. Final Answer:

   Recursion: left, right, then append root -> Option A

4. Quick Check:

   Append after children = postorder collection [OK]

Hint: Append root after children for postorder array [OK]

Common Mistakes:

• Appending root before children (preorder)
• Using queue for level order, not postorder
• Confusing traversal types