BST Property and Why It Matters in DSA Go - Execution Trace

Concept Flow - BST Property and Why It Matters

Start with root node

↓

Check new value vs current node

↓

Go left

↓

Repeat until leaf

↓

Insert new node here

The BST property guides where to place new values by comparing with nodes, going left if smaller, right if larger or equal, until a leaf is found.

Execution Sample

DSA Go

Insert(10)
Insert(5)
Insert(15)
Insert(7)

Insert values into BST following the property: left subtree has smaller values, right subtree has larger or equal values.

Execution Table

Step	Operation	Nodes in Tree	Pointer Changes	Visual State
1	Insert 10 as root	10	root -> 10	10 -> null
2	Insert 5: 5 < 10, go left	10 -> 5	10.left -> 5	10 / 5 -> null
3	Insert 15: 15 >= 10, go right	10 -> 5, 15	10.right -> 15	10 / \ 5 15 -> null
4	Insert 7: 7 < 10, go left; 7 >= 5, go right	10 -> 5 -> 7, 15	5.right -> 7	10 / \ 5 15 \ 7 -> null
5	End of insertions	10 -> 5 -> 7, 15	No pointer changes	10 / \ 5 15 \ 7 -> null

💡 All values inserted following BST property; no more insertions.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
root	null	10	10	10	10	10
current	null	10	10	10	5	null
10.left	null	null	5	5	5	5
10.right	null	null	null	15	15	15
5.right	null	null	null	null	7	7

Key Moments - 3 Insights

Why do we go left when the new value is smaller than the current node?

Because the BST property requires all smaller values to be in the left subtree, as shown in execution_table step 2 where 5 < 10 leads to left insertion.

Why do we go right when the new value is equal or larger than the current node?

The BST property places equal or larger values in the right subtree, ensuring order. See step 3 where 15 >= 10 goes right.

What happens if we reach a null pointer during traversal?

We insert the new node there. In step 4, after going left and then right, 7 is inserted where 5.right was null.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which pointer changes to insert 15?

A 10.left

B 10.right

C 5.left

D 5.right

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

At which step does the tree first have a node with two children?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'Visual State' column and see when root 10 has both left and right children.

If we insert a value 5 again after step 4, where will it be placed?

A Left of 5

B Left of 7

C Right of 5

D Right of 7

💡 Hint

Recall BST property: equal or larger values go right; see step 4 traversal for 7.

Concept Snapshot

BST Property:
- Left subtree nodes < current node
- Right subtree nodes >= current node
Insertion:
- Compare new value with current node
- Go left if smaller, right if larger or equal
- Insert at null pointer
Maintains sorted order for fast search

Full Transcript

The BST property means every node's left subtree has smaller values and right subtree has larger or equal values. When inserting, we start at the root and compare the new value. If smaller, we go left; if larger or equal, we go right. We repeat until we find a null spot to insert the new node. This keeps the tree ordered for efficient searching. For example, inserting 10 creates the root. Inserting 5 goes left of 10. Inserting 15 goes right of 10. Inserting 7 goes right of 5. This process ensures the BST property is always maintained.

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