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

Tree Traversal Inorder Left Root Right

📖 Scenario: Imagine you have a family tree stored as a binary tree. You want to visit each family member in a special order: first the left child, then the parent, then the right child. This is called inorder traversal.

🎯 Goal: Build a simple binary tree and write code to traverse it inorder (left, root, right). Print the values of the nodes in this order.

📋 What You'll Learn

Create a binary tree with exactly 3 nodes: root with value 2, left child with value 1, right child with value 3

Create a function called inorderTraversal that takes the root node and returns a slice of integers representing the inorder traversal

Use recursion to visit left child, root, then right child

Print the slice returned by inorderTraversal

💡 Why This Matters

🌍 Real World

Tree traversals are used in many applications like searching, sorting, and organizing hierarchical data such as file systems or family trees.

💼 Career

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

1

Create the binary tree nodes

Create a struct type called TreeNode with fields Val int, Left *TreeNode, and Right *TreeNode. Then create three variables: root with value 2, root.Left with value 1, and root.Right with value 3.

DSA Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Create root node and its children
// Your code here

Hint

Define the struct first. Then create the root node with value 2. Assign left and right children with values 1 and 3.

2

Create a slice to hold traversal result

Inside main, create a variable called result of type []int to store the values during traversal.

DSA Go

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    root := &TreeNode{Val: 2}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 3}

    // Create a slice called result to hold traversal values
    // Your code here
}

Hint

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

3

Write the inorder traversal function

Write a function called inorderTraversal that takes a parameter node *TreeNode and returns a []int. Use recursion to visit the left child, then append the current node's value, then visit the right child. Combine the results and return the slice.

DSA Go

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    root := &TreeNode{Val: 2}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 3}

    result := []int{}
}

// Write inorderTraversal function here
// Your code here

Hint

Check if node is nil, return empty slice. Recursively get left and right slices. Append left + current value + right.

4

Call traversal and print result

In main, call inorderTraversal(root) and assign the result to result. Then print result using fmt.Println. Import fmt package at the top.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderTraversal(node *TreeNode) []int {
    if node == nil {
        return []int{}
    }
    left := inorderTraversal(node.Left)
    right := inorderTraversal(node.Right)
    return append(append(left, node.Val), right...)
}

func main() {
    root := &TreeNode{Val: 2}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 3}

    result := []int{}

    // Call inorderTraversal and print result
    // Your code here
}

Hint

Assign result = inorderTraversal(root) and print it with fmt.Println(result).

Practice

1. What is the order of nodes visited in an inorder traversal of a binary tree?

easy

A. Root node, Right subtree, Left subtree

B. Root node, Left subtree, Right subtree

C. Right subtree, Root node, Left subtree

D. Left subtree, Root node, Right subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal means visiting the left subtree first, then the root node, and finally the right subtree.

2. Step 2: Apply the traversal order

   Following this order ensures nodes are visited in ascending order for binary search trees.

3. Final Answer:

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

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder = Left, Root, Right [OK]

Common Mistakes:

• Confusing inorder with preorder or postorder
• Visiting root before left subtree
• Visiting right subtree before root

2. Which of the following Go function signatures correctly represents an inorder traversal function for a binary tree node defined as type Node struct { Val int; Left, Right *Node }?

easy

A. func inorder(root *Node) []int

B. func inorder(root Node) []int

C. func inorder(root *Node) int

D. func inorder(root Node) int

Solution

1. Step 1: Understand pointer usage in Go for trees

   Binary trees use pointers to nodes to allow recursive traversal and modification.

2. Step 2: Choose function signature returning slice of ints

   Inorder traversal returns a list of node values, so return type should be []int, and input should be pointer to Node.

3. Final Answer:

   func inorder(root *Node) []int -> Option A

4. Quick Check:

   Pointer receiver and slice return type [OK]

Hint: Use pointer receiver and return slice for traversal [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Returning single int instead of slice
• Using incorrect return type

3. What is the output of the inorder traversal for the following binary tree?

    2
   / \
  1   3

Given the Go code:

type Node struct {
    Val int
    Left, Right *Node
}

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

func main() {
    root := &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}
    result := inorder(root)
    fmt.Println(result)
}

medium

A. [3, 2, 1]

B. [2, 1, 3]

C. [1, 2, 3]

D. [1, 3, 2]

Solution

1. Step 1: Trace inorder traversal on given tree

   Visit left subtree (1), then root (2), then right subtree (3).

2. Step 2: Confirm output list order

   The traversal returns [1, 2, 3] as expected for inorder.

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Inorder traversal output = [1, 2, 3] [OK]

Hint: Inorder visits left, root, then right [OK]

Common Mistakes:

• Appending root before left subtree
• Appending right subtree before root
• Confusing preorder or postorder output

4. The following Go code attempts inorder traversal but produces incorrect output. What is the bug?

func inorder(root *Node) []int {
    if root == nil {
        return []int{}
    }
    left := inorder(root.Left)
    right := inorder(root.Right)
    return append(left, right...)
    return append(result, root.Val)
}

medium

A. The root value is appended after the return statement, so never executed

B. The function should return int, not []int

C. The base case should return nil, not empty slice

D. The left subtree is not traversed

Solution

1. Step 1: Analyze return statements in function

   The first return statement returns append(left, right...), so the second return is unreachable.

2. Step 2: Identify missing root value append

   Root value is never appended because code after first return is ignored.

3. Final Answer:

   The root value is appended after the return statement, so never executed -> Option A

4. Quick Check:

   Code after return is unreachable [OK]

Hint: Check for unreachable code after return [OK]

Common Mistakes:

• Ignoring unreachable code after return
• Not appending root value in correct order
• Confusing base case return value

5. Given a binary tree where some nodes have only one child, how does inorder traversal help in printing the nodes in sorted order if the tree is a binary search tree? Consider the tree:

      5
     / \
    3   8
     \   \
      4   10

What is the inorder traversal output?

hard

A. [5, 3, 4, 8, 10]

B. [3, 4, 5, 8, 10]

C. [4, 3, 5, 10, 8]

D. [3, 5, 4, 8, 10]

Solution

1. Step 1: Apply inorder traversal on given tree

   Visit left subtree: node 3, then its right child 4, then root 5, then right subtree nodes 8 and 10.

2. Step 2: List nodes in inorder sequence

   Sequence is 3, 4, 5, 8, 10 which is sorted ascending order.

3. Final Answer:

   [3, 4, 5, 8, 10] -> Option B

4. Quick Check:

   Inorder traversal of BST gives sorted nodes [OK]

Hint: Inorder traversal of BST prints nodes sorted [OK]

Common Mistakes:

• Ignoring nodes with single child
• Visiting root before left subtree
• Mixing preorder or postorder with inorder