BST Property and Why It Matters in DSA Java

Mental Model

A Binary Search Tree keeps smaller values on the left and bigger values on the right, making searching fast.

Analogy: Imagine a phone book where names are sorted alphabetically; you look left if the name is earlier, right if later, so you find it quickly.

    5
   / \
  3   7
 / \   \
2   4   8

Dry Run Walkthrough

Input: Tree: 5 -> left 3, right 7; Insert 6

Goal: Show how BST property helps find the right place to insert 6 quickly

Step 1: Start at root node 5

    [5↑]
   /   \
  3     7
 / \     \
2   4     8

Why: We begin at the root to decide where to go next

Step 2: Compare 6 with 5; 6 is greater, move right

    5
   / \
  3   [7↑]
 / \    \
2   4    8

Why: BST rule says bigger values go right, so we move right

Step 3: Compare 6 with 7; 6 is smaller, move left

    5
   / \
  3   7
 / \  [null↑]
2   4   8

Why: 6 is less than 7, so it should go to left child of 7

Step 4: Insert 6 as left child of 7

    5
   / \
  3   7
 / \  / \
2   4 6  8

Why: Found empty spot following BST rules, insert here

Result:

    5
   / \
  3   7
 / \  / \
2   4 6  8

Annotated Code

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) {
        this.val = val;
        left = right = null;
    }
}

public class BSTProperty {
    Node root;

    // Insert value following BST property
    Node insert(Node node, int val) {
        if (node == null) {
            return new Node(val); // create new node if spot is empty
        }
        if (val < node.val) {
            node.left = insert(node.left, val); // go left if smaller
        } else if (val > node.val) {
            node.right = insert(node.right, val); // go right if bigger
        }
        return node; // unchanged node
    }

    // Print tree inorder to show sorted order
    void inorder(Node node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.val + " ");
            inorder(node.right);
        }
    }

    public static void main(String[] args) {
        BSTProperty tree = new BSTProperty();
        tree.root = new Node(5);
        tree.root.left = new Node(3);
        tree.root.right = new Node(7);
        tree.root.left.left = new Node(2);
        tree.root.left.right = new Node(4);
        tree.root.right.right = new Node(8);

        tree.root = tree.insert(tree.root, 6); // insert 6

        tree.inorder(tree.root); // print inorder traversal
    }
}

if (node == null) { return new Node(val); }

create new node when empty spot found

if (val < node.val) { node.left = insert(node.left, val); }

go left if value smaller than current node

else if (val > node.val) { node.right = insert(node.right, val); }

go right if value bigger than current node

return node;

return unchanged node after insertion

Output

2 3 4 5 6 7 8 

Complexity Analysis

Time: O(h) where h is tree height, because we follow one path down to insert or search

Space: O(h) due to recursion stack in worst case equal to tree height

vs Alternative: Compared to unsorted tree where insertion/search is O(n), BST property reduces it to O(log n) on balanced trees

Edge Cases

Empty tree

Insertion creates root node

DSA Java

if (node == null) { return new Node(val); }

Insert duplicate value

Duplicate ignored, tree unchanged

DSA Java

else if (val > node.val) { ... } // no insertion if equal

Insert smallest or largest value

Inserted at leftmost or rightmost leaf

DSA Java

if (val < node.val) { ... } else if (val > node.val) { ... }

When to Use This Pattern

When you need fast search, insert, or delete in a sorted structure, look for BST property to guide traversal and keep operations efficient.

Common Mistakes

Mistake: Inserting a value without comparing properly to decide left or right
Fix: Always compare value with current node and go left if smaller, right if bigger

Mistake: Allowing duplicates without handling, causing infinite recursion
Fix: Add condition to ignore or handle duplicates explicitly

Summary

It keeps smaller values left and bigger values right to speed up search and insert.

Use it when you want to organize data for quick lookup and updates.

The key is comparing values at each node to decide direction, avoiding full scans.

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