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 where each person can have children. You want to visit each person starting from the youngest children, then their parents, and finally the oldest ancestor. This is called postorder traversal in trees.

🎯 Goal: You will build a simple tree structure and write code to visit all nodes in postorder (left child, right child, then root) and print their values.

📋 What You'll Learn

Create a class called Node with an integer Value and two children Left and Right

Create a tree with root value 1, left child 2, and right child 3

Add a configuration variable result as a list to store traversal output

Write a recursive method PostorderTraversal that visits left child, right child, then root and adds values to result

Print the result list after traversal

💡 Why This Matters

🌍 Real World

Tree traversal is used in many areas like file system navigation, expression evaluation, and organizing hierarchical data.

💼 Career

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

1

Create the tree nodes

Create a class called Node with an integer property Value and two properties Left and Right of type Node. Then create a root node with Value 1, its left child with Value 2, and right child with Value 3.

DSA C#

// Define class Node and create root with left and right children
// Your code here

Hint

Start by defining the Node class with the properties. Then create the root and assign its children.

2

Add a list to store traversal result

Add a variable called result of type List<int> and initialize it as an empty list to store the values visited during traversal.

DSA C#

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

Node root = new Node(1);
root.Left = new Node(2);
root.Right = new Node(3);

// Create a List called result to store traversal output
// Your code here

Hint

Use List<int> and initialize it with new List<int>().

3

Write the postorder traversal method

Write a recursive method called PostorderTraversal that takes a Node parameter called node. Inside the method, if node is not null, first call PostorderTraversal on node.Left, then on node.Right, and finally add node.Value to the result list.

DSA C#

using System.Collections.Generic;

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

Node root = new Node(1);
root.Left = new Node(2);
root.Right = new Node(3);

List result = new List();

// Write a recursive method PostorderTraversal(Node node) to traverse left, right, then root
// Your code here

Hint

Remember to check if node is not null before recursive calls. Visit left, then right, then add the current node's value.

4

Run traversal and print the result

Call PostorderTraversal with the root node. Then print the result list values separated by spaces.

DSA C#

using System.Collections.Generic;

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

Node root = new Node(1);
root.Left = new Node(2);
root.Right = new Node(3);

List result = new List();

void PostorderTraversal(Node node)
{
    if (node != null)
    {
        PostorderTraversal(node.Left);
        PostorderTraversal(node.Right);
        result.Add(node.Value);
    }
}

// Call PostorderTraversal with root and print the result list separated by spaces
// Your code here

Hint

Call the method with root and use Console.WriteLine(string.Join(" ", result)) to print the values separated by spaces.

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