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.