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

Concept Flow - BST Property and Why It Matters

Start at root node

↓

Compare new value with current node

↓

Go left

↓

Is child null?

↓

Move to [Insert new node here

↓

Done

The BST property guides where to insert or find nodes by comparing values and moving left or right accordingly.

Execution Sample

DSA Java

class Node {
  int val;
  Node left, right;
}

// Insert 7 into BST
insert(root, 7);

Inserts value 7 into the BST by comparing and moving left or right until the correct spot is found.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Start at root	10	7 < 10	None	10
2	Go left	5	7 >= 5	None	10 -> 5
3	Go right	8	7 < 8	None	10 -> 5 -> 8
4	Go left	null	null	Insert 7 as left child of 8	10 -> 5 -> 8 | 7
5	Done	7	Inserted	None	10 -> 5 -> 8 | 7

💡 Insertion done when a null child pointer is found and new node is inserted.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
current	10	10	5	8	7	7
comparison	N/A	7 < 10	7 >= 5	7 < 8	null	null
pointer change	None	None	None	Insert left child	None	None
tree size	3	3	3	3	4	4

Key Moments - 3 Insights

Why do we compare the new value with the current node at each step?

Because the BST property requires left children to be smaller and right children to be greater or equal, so comparison guides the path (see execution_table steps 1-3).

Why do we insert the new node only when we find a null child pointer?

Because a null child pointer means there is no node there yet, so it's the correct place to insert the new node (see execution_table step 4).

Why does the traversal stop after inserting the new node?

Because the BST property is maintained once the new node is inserted, no further traversal is needed (see execution_table step 5).

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node at step 3?

A 8

B 5

C 7

D 10

💡 Hint

Check the 'Current Node' column at step 3 in the execution_table.

At which step is the new node inserted into the BST?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'Insert 7 as left child of 8' in the 'Pointer Changes' column.

If the new value was 12 instead of 7, which direction would the traversal go from the root?

A Left

B Stay at root

C Right

D Insert at root

💡 Hint

Recall BST property: values >= current node go right (see concept_flow).

Concept Snapshot

BST Property:
- Left child < node
- Right child >= node
Insertion:
- Compare new value
- Move left if smaller
- Move right if greater or equal
- Insert at null child
Maintains sorted order for fast search.

Full Transcript

The BST property means every node's left child is smaller and right child is greater or equal. When inserting a new value, start at the root and compare. If the new value is smaller, go left; if greater or equal, go right. Repeat until you find a null child pointer, then insert the new node there. This keeps the tree sorted and allows fast searching and insertion.

Practice

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

easy

A. For each node, all values in the left subtree are smaller, and all values in the right subtree are larger.

B. Each node has exactly two children.

C. All nodes have the same value.

D. Nodes are arranged in a complete binary tree shape.

Solution

1. Step 1: Understand BST definition

   A BST is defined by the order of values: left subtree nodes are smaller, right subtree nodes are larger than the current node.

2. Step 2: Compare options with BST property

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. matches the BST property exactly. Other options describe different tree types or incorrect properties.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option A

4. Quick Check:

   BST property = For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. [OK]

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

Common Mistakes:

• Thinking BST requires exactly two children per node
• Confusing BST with balanced or complete trees
• Assuming all nodes have the same value

2. Which of the following Java method signatures correctly checks if a tree node satisfies the BST property for its immediate children?

easy

A. boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; }

B. boolean isBSTNode(TreeNode node) { return node.left.val > node.val && node.right.val < node.val; }

C. boolean isBSTNode(TreeNode node) { return node.left.val <= node.val && node.right.val >= node.val; }

D. boolean isBSTNode(TreeNode node) { return node.left == null && node.right == null; }

Solution

1. Step 1: Recall BST node condition

   For a node, left child's value must be less than node's value, right child's value must be greater.

2. Step 2: Analyze method signatures

   boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; } correctly checks left.val < node.val and right.val > node.val. Others reverse or relax conditions or check leaf status.

3. Final Answer:

   boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; } -> Option A

4. Quick Check:

   Left < node < Right condition = boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; } [OK]

Hint: Check left < node < right for BST node [OK]

Common Mistakes:

• Using <= or >= instead of < and >
• Swapping left and right comparisons
• Checking if node is leaf instead of BST property

3. Consider the following Java code snippet that inserts values into a BST. What will be the in-order traversal output after inserting 10, 5, 15, 3, 7?

medium

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

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

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

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

Solution

1. Step 1: Insert nodes into BST

   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: 3, 5, 7, 10, 15.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Inserting nodes incorrectly violating BST property
• Forgetting to include all nodes in traversal

4. Given this Java method to check if a tree is a BST, what is the bug?

boolean isBST(TreeNode node, int min, int max) {
  if (node == null) return true;
  if (node.val <= min || node.val >= max) return false;
  return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
}

medium

A. The method should use < and > instead of <= and >= for comparisons.

B. The base case should return false when node is null.

C. The method does not check the entire subtree values properly.

D. The initial call must provide correct min and max values.

Solution

1. Step 1: Understand method logic

   The method uses min and max bounds to check BST property recursively.

2. Step 2: Identify bug

   The method logic is correct, but if initial min and max are not set properly (e.g., Integer.MIN_VALUE and Integer.MAX_VALUE), it may fail.

3. Final Answer:

   The initial call must provide correct min and max values. -> Option D

4. Quick Check:

   Proper initial bounds needed = The initial call must provide correct min and max values. [OK]

Hint: Always start with full integer range for min and max [OK]

Common Mistakes:

• Changing base case to false on null node
• Misusing <= and >= causing off-by-one errors
• Ignoring initial min/max parameters in first call

5. You have a BST where duplicate values are allowed only on the right subtree. Which modification to the BST property is correct to maintain this rule?

hard

A. Left subtree nodes <= node.val, right subtree nodes > node.val

B. Left subtree nodes < node.val, right subtree nodes >= node.val

C. Left subtree nodes <= node.val, right subtree nodes >= node.val

D. Left subtree nodes < node.val, right subtree nodes > node.val

Solution

1. Step 1: Understand duplicate placement rule

   Duplicates allowed only on right subtree means right subtree can have values equal or greater than node.

2. Step 2: Adjust BST property accordingly

   Left subtree must have strictly smaller values, right subtree must have values greater or equal to node.

3. Final Answer:

   Left subtree nodes < node.val, right subtree nodes >= node.val -> Option B

4. Quick Check:

   Duplicates on right = left < node, right >= node [OK]

Hint: Allow equals only on right side with >= [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Using <= on left subtree allowing duplicates there
• Forgetting strict less than on left subtree