Binary Tree Node Structure in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on Binary Tree

What is the output of the inorder traversal on the given binary tree?

DSA Go

package main

import "fmt"

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

func inorder(root *Node) {
    if root == nil {
        return
    }
    inorder(root.Left)
    fmt.Print(root.Val, " -> ")
    inorder(root.Right)
}

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}
    inorder(root)
    fmt.Print("null\n")
}

A 4 -> 2 -> 5 -> 1 -> 3 -> null

B 4 -> 5 -> 2 -> 3 -> 1 -> null

C 1 -> 3 -> 2 -> 4 -> 5 -> null

D 1 -> 2 -> 3 -> 4 -> 5 -> null

💡 Hint

Inorder traversal visits left subtree, then node, then right subtree.

Inorder traversal visits nodes in the order: left child, current node, right child.

For the given tree, the order is 4, 2, 5, 1, 3.

❓ Predict Output

intermediate

Output of Preorder Traversal on Binary Tree

What is the output of the preorder traversal on the given binary tree?

DSA Go

package main

import "fmt"

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

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

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}
    preorder(root)
    fmt.Print("null\n")
}

A 2 -> 4 -> 5 -> 1 -> 3 -> null

B 4 -> 2 -> 5 -> 1 -> 3 -> null

C 1 -> 2 -> 4 -> 5 -> 3 -> null

D 1 -> 3 -> 2 -> 4 -> 5 -> null

💡 Hint

Preorder traversal visits node first, then left subtree, then right subtree.

Preorder traversal visits nodes in the order: current node, left child, right child.

For the given tree, the order is 1, 2, 4, 5, 3.

🔧 Debug

advanced

Identify the Error in Binary Tree Node Initialization

What error will this code produce when trying to create a binary tree node?

DSA Go

package main

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

func main() {
    var root Node
    root.Val = 1
    root.Left.Val = 2
}

A compilation error: cannot assign to struct field

B runtime error: invalid memory address or nil pointer dereference

C no error, code runs successfully

D compilation error: missing type declaration

💡 Hint

Check if the Left pointer is initialized before accessing its fields.

The Left pointer is nil by default and not initialized to point to a Node.

Accessing root.Left.Val causes a runtime nil pointer dereference error.

🧠 Conceptual

advanced

Number of Nodes in a Full Binary Tree of Height h

What is the total number of nodes in a full binary tree of height h (where height is number of edges from root to deepest leaf)?

A 2^h

B 2^h - 1

C 2^(h+1)

D 2^(h+1) - 1

💡 Hint

A full binary tree doubles nodes at each level plus one root.

A full binary tree has nodes count = 2^(height+1) - 1.

Height h means h edges, so levels = h+1.

🚀 Application

expert

Resulting Tree Structure After Insertions

Given an empty binary search tree, insert the values in this order: 10, 5, 15, 3, 7, 12, 18. What is the inorder traversal output?

A 3 -> 5 -> 7 -> 10 -> 12 -> 15 -> 18 -> null

B 10 -> 5 -> 3 -> 7 -> 15 -> 12 -> 18 -> null

C 18 -> 15 -> 12 -> 10 -> 7 -> 5 -> 3 -> null

D 5 -> 3 -> 7 -> 10 -> 15 -> 12 -> 18 -> null

💡 Hint

Inorder traversal of a BST outputs sorted values.

Inserting values in BST order and then inorder traversal outputs sorted values.

The sorted order is 3, 5, 7, 10, 12, 15, 18.

Practice

1. What is the correct way to define a node structure for a binary tree in Go?

easy

A. type Node struct { Value int; Left Node; Right Node }

B. type Node struct { Value int; Left *Node; Right *Node }

C. type Node struct { Value int; Left int; Right int }

D. type Node struct { Value *int; Left *int; Right *int }

Solution

1. Step 1: Understand binary tree node components

   A binary tree node stores a value and pointers to left and right child nodes.

2. Step 2: Check pointer usage in Go struct

   Using pointers (*Node) for Left and Right allows linking nodes without copying entire structs.

3. Final Answer:

   type Node struct { Value int; Left *Node; Right *Node } -> Option B

4. Quick Check:

   Node with pointers = type Node struct { Value int; Left *Node; Right *Node } [OK]

Hint: Use pointers for child nodes to avoid copying structs [OK]

Common Mistakes:

• Using non-pointer types for child nodes causes infinite recursion
• Using int instead of *Node for children
• Using pointers to int instead of pointers to Node

2. Which of the following is the correct syntax to create a new binary tree node with value 10 in Go?

easy

A. node := Node{Value: 10, Left: nil, Right: nil}

B. node := Node(10, nil, nil)

C. node := &Node{Value: 10, Left: nil, Right: nil}

D. node := new(Node{10, nil, nil})

Solution

1. Step 1: Understand node creation with pointers

   To create a pointer to a Node struct, use &Node{...} syntax.

2. Step 2: Check each option's syntax

   node := &Node{Value: 10, Left: nil, Right: nil} correctly creates a pointer to a Node with value 10 and nil children.

3. Final Answer:

   node := &Node{Value: 10, Left: nil, Right: nil} -> Option C

4. Quick Check:

   Pointer node creation uses &Node{...} [OK]

Hint: Use &Node{...} to create pointer nodes [OK]

Common Mistakes:

• Forgetting & to create pointer
• Using new() incorrectly with struct literals
• Calling Node() like a function

3. What will be the output of the following Go code snippet?

package main
import "fmt"

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

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

medium

A. 2

B. 1

C. 3

D. Compilation error

Solution

1. Step 1: Analyze node assignments

   root.Left is assigned a node with Value 2, root.Right with Value 3, root.Value is 1.

2. Step 2: Check printed value

   fmt.Println(root.Left.Value) prints the Value of the left child node, which is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   root.Left.Value = 2 [OK]

Hint: Print child node's Value to get assigned integer [OK]

Common Mistakes:

• Printing root.Value instead of root.Left.Value
• Confusing left and right child values
• Expecting compilation error due to missing import

4. Identify the error in the following Go code defining a binary tree node:

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

func main() {
  root := &Node{Value: 5}
  root.Left = Node{Value: 3}
}

medium

A. Left child should be a pointer to Node, not Node value

B. Right child should not be a pointer

C. Value field must be a pointer to int

D. Cannot assign struct literal to Left field

Solution

1. Step 1: Check struct field types

   Left is declared as Node (value), Right as *Node (pointer). This causes recursive struct size issues.

2. Step 2: Understand pointer necessity

   Binary tree nodes must use pointers for children to avoid infinite size and allow nil values.

3. Final Answer:

   Left child should be a pointer to Node, not Node value -> Option A

4. Quick Check:

   Child nodes must be pointers [OK]

Hint: Use *Node for all child fields to avoid infinite struct size [OK]

Common Mistakes:

• Mixing pointer and value types for children
• Expecting Go to allow recursive value fields
• Ignoring nil possibility for children

5. Given the binary tree node structure below, how would you write a function in Go to insert a new value into a binary search tree?

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

Choose the correct approach.

hard

A. Insert new value at root and push existing nodes down

B. Always insert new value as left child without comparison

C. Use a loop to find nil child and insert without comparison

D. Recursively compare new value with current node; insert left if smaller, right if larger; create new node if nil child

Solution

1. Step 1: Understand binary search tree insertion logic

   New values less than current node go to left subtree; greater go to right subtree.

2. Step 2: Use recursion to find correct insertion point

   Recursively traverse left or right child until a nil child is found, then insert new node there.

3. Final Answer:

   Recursively compare new value with current node; insert left if smaller, right if larger; create new node if nil child -> Option D

4. Quick Check:

   BST insertion uses recursive comparison [OK]

Hint: Compare and recurse left/right until nil, then insert [OK]

Common Mistakes:

• Inserting without comparison breaks BST property
• Always inserting on one side causes imbalance
• Not handling nil child case properly