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

Tree Traversal Preorder Root Left Right

📖 Scenario: Imagine you have a family tree and you want to visit each family member starting from the oldest ancestor, then their children, and so on. This is like walking through a tree data structure in a specific order called preorder traversal.

🎯 Goal: You will build a simple tree structure in Go and write code to visit each node in preorder: first the root, then the left child, then the right child. Finally, you will print the values in the order they are visited.

📋 What You'll Learn

Create a tree node struct with integer values and left/right children

Build a small tree with exactly 3 nodes: root, left child, right child

Write a recursive function called preorder that visits nodes in root-left-right order

Print the values of nodes visited by preorder traversal separated by spaces

💡 Why This Matters

🌍 Real World

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

💼 Career

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

1

Create the Tree Node Structure and Build the Tree

Create a struct called Node with an int field called Value and two pointers to Node called Left and Right. Then create three variables: root with value 1, leftChild with value 2, and rightChild with value 3. Connect root.Left to leftChild and root.Right to rightChild.

DSA Go

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

// Your code here

Hint

Define the Node struct first. Then create pointers to nodes for root, leftChild, and rightChild. Finally, link the children to the root.

2

Add a Slice to Collect Visited Node Values

Create a variable called result of type []int to store the values of nodes visited during preorder traversal.

DSA Go

package main

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func main() {
    root := &Node{Value: 1}
    leftChild := &Node{Value: 2}
    rightChild := &Node{Value: 3}
    root.Left = leftChild
    root.Right = rightChild

    // Create a slice called result to store visited node values
    // Your code here
}

Hint

Use result := []int{} to create an empty slice of integers.

3

Write the Preorder Traversal Function

Write a recursive function called preorder that takes a pointer to Node and a pointer to []int. It should visit the current node first, append its Value to result, then recursively call itself on the Left child, then on the Right child. Call preorder with root and &result inside main.

DSA Go

package main

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func preorder(node *Node, result *[]int) {
    // Your code here
}

func main() {
    root := &Node{Value: 1}
    leftChild := &Node{Value: 2}
    rightChild := &Node{Value: 3}
    root.Left = leftChild
    root.Right = rightChild

    result := []int{}

    // Call preorder with root and &result
    // Your code here
}

Hint

Check if the node is nil to stop recursion. Append the node's value to the slice. Then call preorder on left and right children.

4

Print the Preorder Traversal Result

Print the values stored in result separated by spaces using a for loop inside main.

DSA Go

package main

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func preorder(node *Node, result *[]int) {
    if node == nil {
        return
    }
    *result = append(*result, node.Value)
    preorder(node.Left, result)
    preorder(node.Right, result)
}

func main() {
    root := &Node{Value: 1}
    leftChild := &Node{Value: 2}
    rightChild := &Node{Value: 3}
    root.Left = leftChild
    root.Right = rightChild

    result := []int{}

    preorder(root, &result)

    // Print the values in result separated by spaces
    // Your code here
}

Hint

Use a for loop to print each value. Print a space before each value except the first. End with a newline.