BST Property and Why It Matters in DSA Java - Time & Space Complexity

Time Complexity: BST Property and Why It Matters

O(h)

Understanding Time Complexity

We want to understand how the special rule of a Binary Search Tree (BST) affects how fast we can find or add items.

How does this rule help us do tasks faster as the tree grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public boolean searchBST(TreeNode root, int target) {
    if (root == null) return false;
    if (root.val == target) return true;
    if (target < root.val) return searchBST(root.left, target);
    else return searchBST(root.right, target);
}
    

This code searches for a value in a BST by using the BST property to decide which side to search next.

Identify Repeating Operations

• Primary operation: Recursive calls moving down the tree nodes.
• How many times: At most once per level of the tree until the value is found or no nodes remain.

How Execution Grows With Input

As the tree grows taller, the number of steps to find a value grows with the height of the tree.

Input Size (n)	Approx. Operations (steps down tree)
10	About 3 to 4 steps
100	About 6 to 7 steps
1000	About 9 to 10 steps

Pattern observation: The steps grow slowly, roughly like the height of a balanced tree, not the total number of nodes.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the search time depends on how tall the tree is, not how many total nodes it has.

Common Mistake

[X] Wrong: "Searching a BST always takes time proportional to the number of nodes (n)."

[OK] Correct: Because the BST property lets us skip half the tree at each step, the search depends on the tree height, which can be much smaller than n if the tree is balanced.

Interview Connect

Understanding how the BST property affects search time helps you explain why balanced trees are important and shows you can analyze recursive code clearly.

Self-Check

"What if the BST becomes a linked list (all nodes only have one child)? How would the time complexity change?"

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