Tree Traversal Postorder Left Right Root in DSA C# - Execution Trace

Concept Flow - Tree Traversal Postorder Left Right Root

Start at root node

↓

Traverse left subtree

↓

Traverse right subtree

↓

Visit current node (root)

↓

Back to parent node or end

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

Execution Sample

DSA C#

void PostorderTraversal(Node node) {
  if (node == null) return;
  PostorderTraversal(node.Left);
  PostorderTraversal(node.Right);
  Console.Write(node.Value + " ");
}

This code visits nodes in postorder: left child, right child, then the node itself.

Execution Table

Step	Operation	Node Visited	Left/Right	Tree State
1	Start at root	A	root	A / \ B C
2	Traverse left subtree	B	left of A	A / \ B C
3	Traverse left subtree	D	left of B	A / \ B C / D
4	Traverse left subtree	null	left of D	No change
5	Traverse right subtree	null	right of D	No change
6	Visit node	D	leaf	Output: D
7	Traverse right subtree	E	right of B	A / \ B C \ E
8	Traverse left subtree	null	left of E	No change
9	Traverse right subtree	null	right of E	No change
10	Visit node	E	leaf	Output: D E
11	Visit node	B	left of A	Output: D E B
12	Traverse right subtree	C	right of A	A / \ B C / \ F G
13	Traverse left subtree	F	left of C	No change
14	Traverse left subtree	null	left of F	No change
15	Traverse right subtree	null	right of F	No change
16	Visit node	F	leaf	Output: D E B F
17	Traverse right subtree	G	right of C	No change
18	Traverse left subtree	null	left of G	No change
19	Traverse right subtree	null	right of G	No change
20	Visit node	G	leaf	Output: D E B F G
21	Visit node	C	right of A	Output: D E B F G C
22	Visit node	A	root	Output: D E B F G C A
23	End traversal	null	done	Traversal complete

💡 All nodes visited in postorder: left, right, root.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
Current Node	A	B	D	null	null	D	E	null	null	A
Output	""	""	D	D	D	D	D E	D E	D E	D E B F G C A

Key Moments - 3 Insights

Why do we visit the root node last in postorder traversal?

Because postorder means visiting left subtree, then right subtree, and only then the root node, as shown in steps 6, 10, 11, 16, 20, 21, and finally 22 in the execution_table.

What happens when a node has no left or right child?

The traversal calls on null children (steps 4, 5, 8, 9, 14, 15, 18, 19) which immediately return without action, so the traversal moves on to visit the node itself.

How does the traversal know when to stop?

When all nodes have been visited and recursive calls return back to the root, as shown in step 23 where traversal ends because no more nodes remain.

Visual Quiz - 3 Questions

Look at the execution_table, what is the output after visiting node B (step 11)?

A D E B

B D E

C D E B F

D D E B F G

💡 Hint

Check the 'Output' column at step 11 in the execution_table.

At which step does the traversal visit the root node A?

A Step 21

B Step 22

C Step 20

D Step 23

💡 Hint

Look for 'Visit node A' in the 'Operation' column in the execution_table.

If node C had no right child, how would the output change after step 21?

A Output would be D E B F G C A

B Output would be D E B F A

C Output would be D E B F C A

D Output would be D E B C A

💡 Hint

Compare the output at step 21 and consider missing node G's visit.

Concept Snapshot

Postorder traversal visits nodes in this order:
Left subtree → Right subtree → Root node
Implemented recursively by calling left, then right, then processing the node.
Useful for deleting trees or evaluating expression trees.
Output order: children before parent.

Full Transcript

Postorder traversal means visiting the left child first, then the right child, and finally the node itself. The code recursively calls the traversal on the left subtree, then the right subtree, and then prints the node's value. The execution table shows each step visiting nodes D, E, B, F, G, C, and finally A, producing the output sequence D E B F G C A. When a node has no children, the traversal returns immediately. The traversal ends after all nodes are visited. This method is useful for tasks like deleting nodes or evaluating expressions where children must be processed before parents.

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