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.