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

Tree Traversal Postorder Left Right Root

📖 Scenario: You are working with a simple family tree where each person can have up to two children. You want to visit all family members in a special order: first the left child, then the right child, and finally the parent. This order is called postorder traversal.

🎯 Goal: Build a program that creates a small tree of family members, sets up a function to visit them in postorder (left, right, root), and prints the names in that order.

📋 What You'll Learn

Create a tree node structure with a name string and pointers to left and right children

Build a small tree with exactly these nodes and connections:

"Grandpa" as root, with "Dad" as left child and "Uncle" as right child

"Dad" has "Me" as left child and "Sister" as right child

Write a recursive function called postorder that visits nodes in left, right, root order and collects their names

Print the names in the order they are visited separated by spaces

💡 Why This Matters

🌍 Real World

Tree traversal is used in many areas like file system navigation, organizing family trees, and processing expressions in calculators.

💼 Career

Understanding tree traversal helps in software development roles involving data structures, algorithms, and system design.

1

Create the tree nodes

Create variables called grandpa, dad, uncle, me, and sister of type *Node. Initialize each with the name field set to exactly "Grandpa", "Dad", "Uncle", "Me", and "Sister" respectively. The left and right fields should be nil for now.

DSA Go

package main

type Node struct {
    name  string
    left  *Node
    right *Node
}

func main() {
    // Create nodes grandpa, dad, uncle, me, sister with correct names
    // Your code here
}

Hint

Use &Node{name: "Name"} to create each node. Set left and right to nil by default.

2

Connect the nodes to form the tree

Set the left and right fields to connect the nodes as follows: grandpa.left = dad, grandpa.right = uncle, dad.left = me, and dad.right = sister.

DSA Go

package main

type Node struct {
    name  string
    left  *Node
    right *Node
}

func main() {
    grandpa := &Node{name: "Grandpa"}
    dad := &Node{name: "Dad"}
    uncle := &Node{name: "Uncle"}
    me := &Node{name: "Me"}
    sister := &Node{name: "Sister"}

    // Connect nodes to form the tree
    // Your code here
}

Hint

Assign the child nodes to the left and right fields of their parents.

3

Write the postorder traversal function

Write a recursive function called postorder that takes a *Node and a pointer to a []string. It should visit the left child, then the right child, then add the current node's name to the slice.

DSA Go

package main

type Node struct {
    name  string
    left  *Node
    right *Node
}

func postorder(node *Node, names *[]string) {
    // Visit left child
    // Visit right child
    // Add current node's name
    // Your code here
}

func main() {
    grandpa := &Node{name: "Grandpa"}
    dad := &Node{name: "Dad"}
    uncle := &Node{name: "Uncle"}
    me := &Node{name: "Me"}
    sister := &Node{name: "Sister"}

    grandpa.left = dad
    grandpa.right = uncle
    dad.left = me
    dad.right = sister
}

Hint

Check if node is nil to stop. Then call postorder on left and right. Finally, add node.name to *names.

4

Print the postorder traversal result

Create a slice of strings called names. Call postorder(grandpa, &names). Then print the names separated by spaces using fmt.Println and strings.Join.

DSA Go

package main

import (
    "fmt"
    "strings"
)

type Node struct {
    name  string
    left  *Node
    right *Node
}

func postorder(node *Node, names *[]string) {
    if node == nil {
        return
    }
    postorder(node.left, names)
    postorder(node.right, names)
    *names = append(*names, node.name)
}

func main() {
    grandpa := &Node{name: "Grandpa"}
    dad := &Node{name: "Dad"}
    uncle := &Node{name: "Uncle"}
    me := &Node{name: "Me"}
    sister := &Node{name: "Sister"}

    grandpa.left = dad
    grandpa.right = uncle
    dad.left = me
    dad.right = sister

    // Create names slice, call postorder, print result
    // Your code here
}

Hint

Create an empty slice names. Call postorder(grandpa, &names). Use fmt.Println(strings.Join(names, " ")) to print the names separated by spaces.

Practice

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

easy

A. Root node, Right subtree, Left subtree

B. Root node, Left subtree, Right subtree

C. Left subtree, Right subtree, Root node

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: Match the order with options

   Left subtree, Right subtree, Root node matches the order Left, Right, Root exactly.

3. Final Answer:

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

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember postorder ends with root after children [OK]

Common Mistakes:

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

2. Which of the following Go function signatures correctly represents a recursive postorder traversal of a binary tree node root?

easy

A. func postorder(root *Node) { postorder(root.Left); postorder(root.Right); fmt.Println(root.Value) }

B. func postorder(root *Node) { fmt.Println(root.Value); postorder(root.Left); postorder(root.Right) }

C. func postorder(root *Node) { postorder(root.Right); postorder(root.Left); fmt.Println(root.Value) }

D. func postorder(root *Node) { fmt.Println(root.Value); postorder(root.Right); postorder(root.Left) }

Solution

1. Step 1: Recall postorder traversal steps

   Postorder visits left subtree, then right subtree, then root node.

2. Step 2: Check function calls and print order

   func postorder(root *Node) { postorder(root.Left); postorder(root.Right); fmt.Println(root.Value) } calls postorder on left, then right, then prints root value, matching postorder.

3. Final Answer:

   func postorder(root *Node) { postorder(root.Left); postorder(root.Right); fmt.Println(root.Value) } -> Option A

4. Quick Check:

   Calls: Left, Right, Print root [OK]

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

Common Mistakes:

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

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

      1
     / \
    2   3
   / \
  4   5

func postorder(root *Node) { if root == nil { return } postorder(root.Left) postorder(root.Right) fmt.Print(root.Value, " ") }

medium

A. 4 2 5 3 1

B. 1 2 4 5 3

C. 2 4 5 3 1

D. 4 5 2 3 1

Solution

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

   Left subtree is rooted at 2. Postorder of subtree 2 is: left(4), right(5), root(2) -> 4 5 2.

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), so output 3. Then print root 1 last.

3. Final Answer:

   4 5 2 3 1 -> Option D

4. Quick Check:

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

Hint: Visit left subtree fully, then right, then root [OK]

Common Mistakes:

• Printing root before children
• Mixing left and right subtree order
• Skipping leaf nodes

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

func postorder(root *Node) {
  if root == nil {
    return
  }
  postorder(root.Right)
  postorder(root.Left)
  fmt.Print(root.Value, " ")
}

medium

A. The order of recursive calls is swapped; left should be before right

B. The base case is missing for nil nodes

C. The root value should be printed before recursive calls

D. The function should return a slice instead of printing

Solution

1. Step 1: Analyze recursive call order

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

2. Step 2: Recall correct postorder sequence

   Postorder requires left subtree first, then right subtree, then root. Swapping left and right causes wrong output.

3. Final Answer:

   The order of recursive calls is swapped; left should be before right -> Option A

4. Quick Check:

   Left before Right in postorder [OK]

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

Common Mistakes:

• Swapping left and right subtree calls
• Printing root before children
• Ignoring base case for nil

5. You want to collect the values of a binary tree in postorder traversal into a slice instead of printing. Which Go function correctly implements this?

hard

A. func postorder(root *Node, res *[]int) {
if root == nil {
return
}
postorder(root.Right, res)
postorder(root.Left, res)
*res = append(*res, root.Value)
}

B. func postorder(root *Node) []int {
if root == nil {
return []int{}
}
left := postorder(root.Left)
right := postorder(root.Right)
return append(left, append(right, root.Value)...)
}

C. func postorder(root *Node, res *[]int) {
if root == nil {
return
}
*res = append(*res, root.Value)
postorder(root.Left, res)
postorder(root.Right, res)
}

D. func postorder(root *Node) []int {
if root == nil {
return nil
}
return []int{root.Value}
}

Solution

1. Step 1: Understand collecting values in slice recursively

   We want a function returning a slice with postorder values: left subtree slice + right subtree slice + root value.

2. Step 2: Check each option for correct order and slice handling

   func postorder(root *Node) []int { if root == nil { return []int{} } left := postorder(root.Left) right := postorder(root.Right) return append(left, append(right, root.Value)...) } correctly returns left slice, then appends right slice, then root value, matching postorder traversal.

3. Final Answer:

   func postorder(root *Node) []int { if root == nil { return []int{} } left := postorder(root.Left) right := postorder(root.Right) return append(left, append(right, root.Value)...) } -> Option B

4. Quick Check:

   Return slices: left + right + root [OK]

Hint: Return left + right + root slices combined [OK]

Common Mistakes:

• Appending root before children slices
• Not combining slices correctly
• Returning nil instead of empty slice for nil node