Tree Traversal Preorder Root Left Right in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Preorder traversal output of a simple binary tree

What is the output of the preorder traversal (Root, Left, Right) for the given binary tree?

DSA Go

package main

import "fmt"

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

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

func main() {
    root := &Node{Val: 1}
    root.Left = &Node{Val: 2}
    root.Right = &Node{Val: 3}
    root.Left.Left = &Node{Val: 4}
    root.Left.Right = &Node{Val: 5}
    fmt.Println(preorder(root))
}

A [1 2 4 5 3]

B [1 3 2 4 5]

C [4 2 5 1 3]

D [2 4 5 1 3]

💡 Hint

Remember preorder means visit root first, then left subtree, then right subtree.

Preorder traversal visits the root node first, then recursively visits the left subtree, and finally the right subtree. So the output is 1 (root), then 2 (left child), then 4 (left-left child), then 5 (left-right child), then 3 (right child).

❓ Predict Output

intermediate

Preorder traversal output with a missing right subtree

What is the output of the preorder traversal for the binary tree where the right subtree is missing?

DSA Go

package main

import "fmt"

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

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

func main() {
    root := &Node{Val: 10}
    root.Left = &Node{Val: 20}
    root.Left.Left = &Node{Val: 30}
    fmt.Println(preorder(root))
}

A [30 20 10]

B [20 30 10]

C [10 30 20]

D [10 20 30]

💡 Hint

Preorder visits root first, then left subtree, then right subtree (which is empty here).

The preorder traversal visits 10 first (root), then 20 (left child), then 30 (left-left child). There is no right subtree, so traversal ends.

🔧 Debug

advanced

Identify the error in preorder traversal implementation

What error will this preorder traversal code cause when run?

DSA Go

package main

import "fmt"

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

func preorder(root *Node) []int {
    if root == nil {
        return nil
    }
    result := []int{}
    result = append(result, preorder(root.Left)...) // line A
    result = append(result, root.Val)               // line B
    result = append(result, preorder(root.Right)...)// line C
    return result
}

func main() {
    root := &Node{Val: 1}
    root.Left = &Node{Val: 2}
    root.Right = &Node{Val: 3}
    fmt.Println(preorder(root))
}

A Output: [2 3 1]

B Output: [1 2 3]

C Output: [2 1 3]

D Output: []

💡 Hint

Check the order of appending values in preorder traversal.

The code appends left subtree first, then root value, then right subtree. This is actually inorder traversal, not preorder. So output is [2 1 3].

🧠 Conceptual

advanced

Number of nodes visited in preorder traversal

Given a binary tree with 7 nodes, how many nodes will preorder traversal visit?

A 7

B Depends on the tree structure

C 8

D 6

💡 Hint

Preorder traversal visits every node exactly once.

Preorder traversal visits every node in the tree exactly once, so for 7 nodes, it visits 7 nodes.

🚀 Application

expert

Preorder traversal output of a complex tree

What is the preorder traversal output of the following tree? 5 / \ 3 8 / / \ 1 6 9 7

DSA Go

package main

import "fmt"

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

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

func main() {
    root := &Node{Val: 5}
    root.Left = &Node{Val: 3}
    root.Right = &Node{Val: 8}
    root.Left.Left = &Node{Val: 1}
    root.Right.Left = &Node{Val: 6}
    root.Right.Right = &Node{Val: 9}
    root.Right.Left.Right = &Node{Val: 7}
    fmt.Println(preorder(root))
}

A [5 8 6 7 9 3 1]

B [5 3 1 8 6 7 9]

C [5 3 1 8 6 9 7]

D [1 3 5 6 7 8 9]

💡 Hint

Remember preorder visits root, then left subtree, then right subtree recursively.

Preorder visits 5 (root), then left subtree: 3, then 1; then right subtree: 8, then 6, then 7, then 9.

Practice

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

easy

A. Root, Left, Right

B. Left, Root, Right

C. Left, Right, Root

D. Right, Left, Root

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then the left subtree, and finally the right subtree.

2. Step 2: Match the order with options

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

3. Final Answer:

   Root, Left, Right -> Option A

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Remember preorder starts with root node first [OK]

Common Mistakes:

• Confusing preorder with inorder or postorder
• Swapping left and right subtree order
• Starting traversal from left child instead of root

2. Which of the following Go function signatures correctly represents a preorder traversal function for a binary tree node Node?

easy

A. func preorder(root *Node) { if root == nil { return } preorder(root.Left) preorder(root.Right) fmt.Println(root.Value) }

B. func preorder(root *Node) { if root == nil { return } fmt.Println(root.Value) preorder(root.Left) preorder(root.Right) }

C. func preorder(root *Node) { if root == nil { return } preorder(root.Right) fmt.Println(root.Value) preorder(root.Left) }

D. func preorder(root *Node) { if root == nil { return } preorder(root.Left) fmt.Println(root.Value) preorder(root.Right) }

Solution

1. Step 1: Recall preorder traversal order

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Check function order

   func preorder(root *Node) { if root == nil { return } fmt.Println(root.Value) preorder(root.Left) preorder(root.Right) } prints root value first, then recursively visits left and right children, matching preorder.

3. Final Answer:

   func preorder(root *Node) { if root == nil { return } fmt.Println(root.Value) preorder(root.Left) preorder(root.Right) } -> Option B

4. Quick Check:

   Print root before children calls [OK]

Hint: Print root value before recursive calls [OK]

Common Mistakes:

• Printing after recursive calls (postorder)
• Swapping left and right recursive calls
• Missing nil check for root

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

    10
   /  \
  5    15
 /    /  \
3    12  20

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

medium

A. [5, 3, 10, 15, 12, 20]

B. [3, 5, 10, 12, 15, 20]

C. [10, 15, 20, 12, 5, 3]

D. [10, 5, 3, 15, 12, 20]

Solution

1. Step 1: Start at root node 10

   Print 10, then traverse left subtree.

2. Step 2: Traverse left subtree (5, then 3)

   Print 5, then left child 3, which has no children.

3. Step 3: Traverse right subtree (15, 12, 20)

   Print 15, then left child 12, then right child 20.

4. Final Answer:

   [10, 5, 3, 15, 12, 20] -> Option D

5. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Follow root, then left subtree, then right subtree order [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder output
• Visiting right subtree before left
• Skipping leaf nodes

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

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

medium

A. The function uses fmt.Print instead of fmt.Println

B. The function does not check for nil root

C. The root value is printed after left subtree traversal, not before

D. The right subtree is traversed before the left subtree

Solution

1. Step 1: Analyze print position in code

   The root value is printed after preorder(root.Left), so root is visited after left subtree.

2. Step 2: Compare with preorder definition

   Preorder requires visiting root first, then left, then right. This code visits left first, then root, then right (inorder).

3. Final Answer:

   The root value is printed after left subtree traversal, not before -> Option C

4. Quick Check:

   Print root before children for preorder [OK]

Hint: Print root value before recursive calls to fix order [OK]

Common Mistakes:

• Confusing preorder with inorder traversal
• Ignoring nil check (though present here)
• Thinking print function choice affects traversal order

5. You want to collect all node values of a binary tree in preorder traversal into a slice in Go. Which code snippet correctly does this?

hard

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

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

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

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

Solution

1. Step 1: Understand preorder collection logic

   Preorder means add root value first, then traverse left and right subtrees.

2. Step 2: Check each option's order and parameter usage

   func preorder(root *Node, result *[]int) { if root == nil { return } *result = append(*result, root.Value) preorder(root.Left, result) preorder(root.Right, result) } appends root value first, then recursively traverses left and right, using pointer to slice to collect values correctly.

3. Final Answer:

   func preorder(root *Node, result *[]int) { if root == nil { return } *result = append(*result, root.Value) preorder(root.Left, result) preorder(root.Right, result) } -> Option A

4. Quick Check:

   Append root first, use pointer to slice [OK]

Hint: Append root value before recursive calls, pass slice pointer [OK]

Common Mistakes:

• Appending after recursive calls (wrong order)
• Passing slice by value and expecting changes
• Appending right subtree before left subtree