BST Property and Why It Matters in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inserting Nodes in BST

What is the printed state of the BST after inserting the values 10, 5, 15, 3, 7 in that order? The BST property is maintained during insertion.

DSA Go

package main

import "fmt"

type Node struct {
    val   int
    left  *Node
    right *Node
}

func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val < root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}

func inorder(root *Node) {
    if root == nil {
        return
    }
    inorder(root.left)
    fmt.Print(root.val, " -> ")
    inorder(root.right)
}

func main() {
    var root *Node
    vals := []int{10, 5, 15, 3, 7}
    for _, v := range vals {
        root = insert(root, v)
    }
    inorder(root)
    fmt.Print("null\n")
}

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

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

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

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

💡 Hint

Remember that inorder traversal of a BST prints values in ascending order.

Inorder traversal of a BST visits nodes in ascending order because left subtree nodes are smaller, root is next, then right subtree nodes are larger.

Inserted values 10, 5, 15, 3, 7 create a BST where inorder traversal prints: 3 -> 5 -> 7 -> 10 -> 15 -> null.

🧠 Conceptual

intermediate

Why BST Property Matters for Search Efficiency

Why does maintaining the BST property help in searching for a value efficiently?

A Because it sorts values after every insertion to speed up search.

B Because it stores all values in a linked list for quick access.

C Because it allows skipping half of the tree at each step, similar to binary search.

D Because it uses hashing to find values instantly.

💡 Hint

Think about how binary search works on sorted arrays.

The BST property ensures left children are smaller and right children are larger than the node, allowing the search to decide which subtree to explore next.

This halves the search space at each step, making search efficient like binary search.

🔧 Debug

advanced

Identify the Error in BST Insertion Code

What error will this Go code produce when inserting values into a BST?

DSA Go

func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val <= root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}

// Node struct is defined as usual.

A Runtime panic due to nil pointer dereference.

B Stack overflow due to infinite recursion on duplicates.

C Compilation error due to missing return statement.

D No error; duplicates go to left subtree.

💡 Hint

Check how duplicates are handled in the code.

The code allows duplicates by inserting them into the left subtree (val <= root.val).

This is valid and will not cause errors or infinite recursion.

❓ Predict Output

advanced

Output After Deleting a Node in BST

Given a BST with nodes 20, 10, 30, 5, 15, what is the inorder traversal output after deleting node 10?

DSA Go

package main

import "fmt"

type Node struct {
    val   int
    left  *Node
    right *Node
}

func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val < root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}

func minValueNode(node *Node) *Node {
    current := node
    for current.left != nil {
        current = current.left
    }
    return current
}

func deleteNode(root *Node, val int) *Node {
    if root == nil {
        return root
    }
    if val < root.val {
        root.left = deleteNode(root.left, val)
    } else if val > root.val {
        root.right = deleteNode(root.right, val)
    } else {
        if root.left == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    }
    return root
}

func inorder(root *Node) {
    if root == nil {
        return
    }
    inorder(root.left)
    fmt.Print(root.val, " -> ")
    inorder(root.right)
}

func main() {
    var root *Node
    vals := []int{20, 10, 30, 5, 15}
    for _, v := range vals {
        root = insert(root, v)
    }
    root = deleteNode(root, 10)
    inorder(root)
    fmt.Print("null\n")
}

A 5 -> 15 -> 20 -> 30 -> null

B 5 -> 10 -> 15 -> 20 -> 30 -> null

C 15 -> 5 -> 20 -> 30 -> null

D 5 -> 20 -> 30 -> null

💡 Hint

When deleting a node with two children, replace it with the smallest node in the right subtree.

Node 10 has two children (5 and 15). Deleting it replaces 10 with 15 (smallest in right subtree).

Inorder traversal after deletion: 5 -> 15 -> 20 -> 30 -> null.

🧠 Conceptual

expert

Effect of Violating BST Property on Search

If a binary tree does not maintain the BST property, what is the impact on search operation efficiency?

A Search becomes constant time because nodes are unordered.

B Search becomes linear time, similar to searching an unsorted list.

C Search remains logarithmic time due to tree structure.

D Search cannot be performed at all.

💡 Hint

Think about how the BST property helps reduce search space.

Without BST property, you cannot decide which subtree to explore, so you may need to check every node.

This makes search time linear, like scanning a list.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. Nodes are arranged in a complete binary tree shape

B. Left child nodes have smaller values, right child nodes have larger values

C. All nodes have exactly two children

D. Nodes store only unique values without any order

Solution

1. Step 1: Understand BST node arrangement

   In a BST, each node's left child contains values smaller than the node, and the right child contains values larger than the node.

2. Step 2: Compare with other tree types

   Other options describe different tree properties, but only Left child nodes have smaller values, right child nodes have larger values matches the BST property.

3. Final Answer:

   Left child nodes have smaller values, right child nodes have larger values -> Option B

4. Quick Check:

   BST property = Left smaller, right larger [OK]

Hint: Remember BST orders left < node < right [OK]

Common Mistakes:

• Confusing BST with complete binary tree
• Thinking all nodes must have two children
• Ignoring the order property of BST

2. Which of the following Go struct definitions correctly represents a node in a BST?

easy

A. type Node struct { value int; left Node; right Node }

B. type Node struct { value int; left *int; right *int }

C. type Node struct { value int; left *Node; right *Node }

D. type Node struct { value int; left interface{}; right interface{} }

Solution

1. Step 1: Check pointer usage for child nodes

   In Go, child nodes must be pointers to allow nil and recursive structure. type Node struct { value int; left *Node; right *Node } uses *Node pointers correctly.

2. Step 2: Identify incorrect struct fields

   type Node struct { value int; left Node; right Node } uses Node directly, causing infinite size. type Node struct { value int; left *int; right *int } uses *int which is wrong type. type Node struct { value int; left interface{}; right interface{} } uses interface{}, losing type safety.

3. Final Answer:

   type Node struct { value int; left *Node; right *Node } -> Option C

4. Quick Check:

   Use pointers for recursive structs in Go [OK]

Hint: Use *Node for left and right child pointers [OK]

Common Mistakes:

• Using struct fields instead of pointers for children
• Using wrong pointer types like *int
• Using interface{} losing type safety

3. What will be the in-order traversal output of this BST after inserting values in order: 10, 5, 15, 3, 7?

package main
import "fmt"
type Node struct {
  value int
  left, right *Node
}
func inOrder(root *Node) {
  if root == nil {
    return
  }
  inOrder(root.left)
  fmt.Print(root.value, " ")
  inOrder(root.right)
}
func insert(root *Node, val int) *Node {
  if root == nil {
    return &Node{value: val}
  }
  if val < root.value {
    root.left = insert(root.left, val)
  } else {
    root.right = insert(root.right, val)
  }
  return root
}
func main() {
  var root *Node
  vals := []int{10, 5, 15, 3, 7}
  for _, v := range vals {
    root = insert(root, v)
  }
  inOrder(root)
}

medium

A. 3 5 7 10 15

B. 10 5 15 3 7

C. 15 10 7 5 3

D. 5 3 7 10 15

Solution

1. Step 1: Insert values maintaining BST property

   Insert 10 as root, 5 to left, 15 to right, 3 left of 5, 7 right of 5.

2. Step 2: Perform in-order traversal

   In-order visits left subtree, node, right subtree. So output is 3 5 7 10 15.

3. Final Answer:

   3 5 7 10 15 -> Option A

4. Quick Check:

   In-order traversal of BST = sorted values [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Not inserting nodes correctly in BST
• Printing values in insertion order

4. The following Go code tries to insert a value into a BST but fails to correctly insert the value. What is the bug?

func insert(root *Node, val int) *Node {
  if root == nil {
    return &Node{value: val}
  }
  if val <= root.value {
    insert(root.left, val)
  } else {
    insert(root.right, val)
  }
  return root
}

medium

A. Missing assignment to root.left or root.right after recursive insert

B. Using <= instead of < causes infinite recursion

C. Returning root instead of new node causes error

D. Function should not return *Node

Solution

1. Step 1: Analyze recursive insert calls

   The recursive calls insert(root.left, val) and insert(root.right, val) do not assign the returned node back to root.left or root.right.

2. Step 2: Understand why assignment is needed

   Without assignment, new nodes are not linked to the tree, causing incorrect structure.

3. Final Answer:

   Missing assignment to root.left or root.right after recursive insert -> Option A

4. Quick Check:

   Assign recursive insert result to child pointers [OK]

Hint: Always assign recursive insert result to child pointers [OK]

Common Mistakes:

• Forgetting to assign recursive call results
• Confusing comparison operators causing infinite loops
• Ignoring return values in recursive functions

5. You want to check if a binary tree is a valid BST. Which approach correctly verifies the BST property for all nodes?

hard

A. Check only immediate children values against node

B. Check in-order traversal for duplicates only

C. Check tree balance and uniqueness of values

D. Recursively verify all subtree values against node limits

Solution

1. Step 1: Understand BST validation requirements

   BST property requires all nodes in left subtree to be less than current node and all in right subtree to be greater, not just immediate children.

2. Step 2: Evaluate each option

   Recursively verify all subtree values against node limits correctly checks recursively with value limits. Check only immediate children values against node only checks immediate children, which can miss violations deeper in the tree.

3. Final Answer:

   Recursively verify all subtree values against node limits -> Option D

4. Quick Check:

   BST validation = recursive range checks [OK]

Hint: Check all subtree values recursively, not just children [OK]

Common Mistakes:

• Checking only immediate children values
• Confusing balance with BST property
• Assuming no duplicates means valid BST