Tree Traversal Postorder Left Right Root in DSA C#

Mental Model

Visit the left child, then the right child, and finally the node itself. This order ensures children are processed before their parent.

Analogy: Imagine cleaning a family house: first clean the left room, then the right room, and only after both rooms are clean, clean the main hall.

    1
   / \
  2   3
 / \
4   5
↑ root

Dry Run Walkthrough

Input: Tree: 1 with left child 2 and right child 3; 2 has children 4 (left) and 5 (right)

Goal: Print nodes in postorder: left subtree, right subtree, then root

Step 1: Traverse left subtree of root (1), move to node 2

1 -> [curr->2] -> 3
2 -> 4 (left), 5 (right)
↑ at 2

Why: We must visit left child before root

Step 2: Traverse left subtree of 2, move to node 4

2 -> [curr->4] -> 5
4 is leaf
↑ at 4

Why: Left subtree of 2 must be visited first

Step 3: Visit node 4 (leaf), print 4

4 visited
Output: 4

Why: Leaf nodes are printed immediately

Step 4: Traverse right subtree of 2, move to node 5

2 -> 4 (visited), [curr->5]
5 is leaf
↑ at 5

Why: After left child, visit right child

Step 5: Visit node 5, print 5

5 visited
Output: 4 5

Why: Leaf nodes are printed immediately

Step 6: Visit node 2 after children, print 2

2 visited
Output: 4 5 2

Why: Root printed after children

Step 7: Traverse right subtree of root (1), move to node 3

1 -> 2 (visited), [curr->3]
3 is leaf
↑ at 3

Why: Right child visited after left subtree

Step 8: Visit node 3, print 3

3 visited
Output: 4 5 2 3

Why: Leaf nodes printed immediately

Step 9: Visit root node 1 after children, print 1

1 visited
Output: 4 5 2 3 1

Why: Root printed last

Result:

4 -> 5 -> 2 -> 3 -> 1 -> null
Output: 4 5 2 3 1

Annotated Code

DSA C#

using System;

class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree
{
    public Node root;

    // Postorder traversal: left, right, root
    public void Postorder(Node node)
    {
        if (node == null)
            return; // base case: no node to process

        Postorder(node.left); // traverse left subtree
        Postorder(node.right); // traverse right subtree
        Console.Write(node.data + " "); // visit root
    }

    static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        tree.Postorder(tree.root);
        Console.WriteLine();
    }
}

if (node == null) return;

stop recursion when no node

Postorder(node.left);

traverse left subtree first

Postorder(node.right);

then traverse right subtree

Console.Write(node.data + " ");

visit current node after children

Output

4 5 2 3 1 

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative traversal, recursive postorder is simpler but uses call stack; iterative may use explicit stack with similar time

Edge Cases

Empty tree (root is null)

No output, function returns immediately

DSA C#

if (node == null)
    return;

Single node tree

Prints the single node value

DSA C#

if (node == null)
    return;

Tree with only left children

Visits all left nodes in order from bottom to top

DSA C#

Postorder(node.left);

When to Use This Pattern

When you need to process children before their parent in a tree, use postorder traversal to ensure left and right subtrees are handled first.

Common Mistakes

Mistake: Visiting the root node before children (preorder) instead of after
Fix: Move the print statement after recursive calls to left and right children

Mistake: Forgetting to check for null nodes causing errors
Fix: Add base case to return immediately if node is null

Summary

Visits left subtree, then right subtree, then the root node.

Use when you want to process children before their parent, such as deleting a tree or evaluating expressions.

The key is to visit the root only after both left and right children are fully processed.

Practice

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

easy

A. Left subtree, Right subtree, Root node

B. Root node, Left subtree, Right subtree

C. Root node, Right subtree, Left subtree

D. Right subtree, Left 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: Confirm the visiting order

   This order ensures children nodes are processed before their parent node.

3. Final Answer:

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

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 node first instead of last
• Swapping left and right subtree order

2. Which of the following C# method signatures correctly represents a postorder traversal of a binary tree node named root?

easy

A. void PostorderTraversal(Node root) { PostorderTraversal(root.Right); PostorderTraversal(root.Left); Console.WriteLine(root.Value); }

B. void PostorderTraversal(Node root) { Console.WriteLine(root.Value); PostorderTraversal(root.Left); PostorderTraversal(root.Right); }

C. void PostorderTraversal(Node root) { PostorderTraversal(root.Left); PostorderTraversal(root.Right); Console.WriteLine(root.Value); }

D. void PostorderTraversal(Node root) { Console.WriteLine(root.Value); PostorderTraversal(root.Right); PostorderTraversal(root.Left); }

Solution

1. Step 1: Identify correct postorder call sequence

   Postorder traversal calls left subtree, then right subtree, then processes the root.

2. Step 2: Match method calls to postorder order

   void PostorderTraversal(Node root) { PostorderTraversal(root.Left); PostorderTraversal(root.Right); Console.WriteLine(root.Value); } calls left, then right, then prints root value, matching postorder traversal.

3. Final Answer:

   void PostorderTraversal(Node root) { PostorderTraversal(root.Left); PostorderTraversal(root.Right); Console.WriteLine(root.Value); } -> Option C

4. Quick Check:

   Left, Right, Root call order = void PostorderTraversal(Node root) { PostorderTraversal(root.Left); PostorderTraversal(root.Right); Console.WriteLine(root.Value); } [OK]

Hint: Postorder prints after left and right recursive calls [OK]

Common Mistakes:

• Printing root value before recursive calls
• Swapping left and right subtree calls
• Missing recursive calls for subtrees

3. Given the binary tree below, what is the output of a postorder traversal?

    1
   / \
  2   3
 / \
4   5

medium

A. [1, 2, 3, 4, 5]

B. [4, 5, 2, 3, 1]

C. [2, 4, 5, 3, 1]

D. [4, 2, 5, 3, 1]

Solution

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

   Left subtree is rooted at 2, with children 4 and 5. Postorder visits 4, then 5, then 2.

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), visited next. Finally, root 1 is visited last.

3. Final Answer:

   [4, 5, 2, 3, 1] -> Option B

4. Quick Check:

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

Hint: Visit children fully before parent in postorder [OK]

Common Mistakes:

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

4. The following C# code attempts a postorder traversal but produces incorrect output. What is the error?

void Postorder(Node root) {
  if (root == null) return;
  Console.WriteLine(root.Value);
  Postorder(root.Left);
  Postorder(root.Right);
}

medium

A. The root value is printed before traversing subtrees

B. The base case for null root is missing

C. Left and right subtree calls are swapped

D. The method does not return any value

Solution

1. Step 1: Analyze the order of operations in code

   The code prints root value first, then traverses left and right subtrees.

2. Step 2: Compare with postorder traversal rules

   Postorder requires visiting left and right subtrees before printing root value.

3. Final Answer:

   Root value printed before subtrees traversal -> Option A

4. Quick Check:

   Postorder prints after children, not before [OK]

Hint: Print root after recursive calls for postorder [OK]

Common Mistakes:

• Printing root before recursive calls
• Ignoring null base case (though present here)
• Swapping left and right subtree calls

5. You want to collect all node values of a binary tree in postorder traversal into a list in C#. Which code snippet correctly implements this?

hard

A. void Postorder(Node root, List<int> result) { if(root == null) return; result.Add(root.Value); Postorder(root.Right, result); Postorder(root.Left, result); }

B. void Postorder(Node root, List<int> result) { if(root == null) return; result.Add(root.Value); Postorder(root.Left, result); Postorder(root.Right, result); }

C. void Postorder(Node root, List<int> result) { if(root == null) return; Postorder(root.Right, result); Postorder(root.Left, result); result.Add(root.Value); }

D. void Postorder(Node root, List<int> result) { if(root == null) return; Postorder(root.Left, result); Postorder(root.Right, result); result.Add(root.Value); }

Solution

1. Step 1: Confirm traversal order in code

   void Postorder(Node root, List<int> result) { if(root == null) return; Postorder(root.Left, result); Postorder(root.Right, result); result.Add(root.Value); } calls left subtree, then right subtree, then adds root value to list, matching postorder.

2. Step 2: Verify list collection logic

   Adding root value after recursive calls ensures correct postorder sequence in the list.

3. Final Answer:

   void Postorder(Node root, List<int> result) { if(root == null) return; Postorder(root.Left, result); Postorder(root.Right, result); result.Add(root.Value); } -> Option D

4. Quick Check:

   Left, Right, Root with Add after recursion [OK]

Hint: Add node value after left and right recursive calls [OK]

Common Mistakes:

• Adding root value before recursive calls
• Swapping left and right subtree calls
• Not handling null root properly