Validate if Tree is BST in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Validation for a Simple Tree

What is the output of the following Java code that checks if a binary tree is a BST?

DSA Java

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

public class ValidateBST {
    static boolean isBST(Node root, Integer min, Integer max) {
        if (root == null) return true;
        if ((min != null && root.val <= min) || (max != null && root.val >= max)) return false;
        return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(2);
        root.left.right = new Node(7);
        root.right.left = new Node(12);
        root.right.right = new Node(20);
        System.out.println(isBST(root, null, null));
    }
}

A false

B true

C Compilation error

D Runtime exception

💡 Hint

Check if all nodes follow BST rules: left < root < right

The tree satisfies BST properties because every node's left subtree contains smaller values and right subtree contains larger values.

❓ Predict Output

intermediate

Output for Tree with Invalid BST Node

What will be the output of this Java code that validates if a binary tree is a BST?

DSA Java

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

public class ValidateBST {
    static boolean isBST(Node root, Integer min, Integer max) {
        if (root == null) return true;
        if ((min != null && root.val <= min) || (max != null && root.val >= max)) return false;
        return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(8); // Invalid: 8 < 10 but on right
        System.out.println(isBST(root, null, null));
    }
}

A true

B Compilation error

C false

D Runtime exception

💡 Hint

Check if right child is greater than root

The right child 8 is less than root 10, violating BST property. So output is false.

🔧 Debug

advanced

Identify the Error in BST Validation Code

What error will this Java code produce when checking if a tree is a BST?

DSA Java

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

public class ValidateBST {
    static boolean isBST(Node root, int min, int max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        System.out.println(isBST(root, null, null));
    }
}

A Compilation error due to passing null to int parameters

B Runtime NullPointerException

C Output is false

D Output is true

💡 Hint

Check parameter types and arguments passed

The method expects int parameters but null is passed, causing a compilation error.

🚀 Application

advanced

Number of Nodes in a Valid BST

Given the following tree, how many nodes does the tree have if it is a valid BST?

DSA Java

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

// Tree structure:
//       8
//      / \
//     3   10
//    / \    \
//   1   6    14
//      / \   /
//     4   7 13

public class CountNodes {
    static int countNodes(Node root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(8);
        root.left = new Node(3);
        root.right = new Node(10);
        root.left.left = new Node(1);
        root.left.right = new Node(6);
        root.left.right.left = new Node(4);
        root.left.right.right = new Node(7);
        root.right.right = new Node(14);
        root.right.right.left = new Node(13);
        System.out.println(countNodes(root));
    }
}

A 9

B 8

C 10

D 7

💡 Hint

Count all nodes in the tree

The tree has 9 nodes total as counted by the recursive function.

🧠 Conceptual

expert

Why Use Min and Max Bounds in BST Validation?

Why does the BST validation algorithm use min and max bounds when checking each node?

A To convert the tree into a sorted list

B To count the number of nodes in the tree efficiently

C To balance the tree during validation

D To ensure each node's value is within the valid range defined by its ancestors, preserving BST property

💡 Hint

Think about how BST property applies to all descendants, not just immediate children

Min and max bounds track the allowed value range for each node based on its ancestors, ensuring the entire subtree respects BST rules.

Practice

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

easy

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

B. Each node has exactly two children

C. All nodes have unique values but no order is required

D. The tree is always balanced

Solution

1. Step 1: Understand BST property

   A BST requires that for every node, values in the left subtree are smaller and values in the right subtree are larger.

2. Step 2: Compare options with BST definition

   For each node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger correctly states this property, while others describe different tree characteristics.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Ignoring the ordering property

2. Which of the following Java method signatures is correct to check if a binary tree is a BST?

easy

A. public int isBST(Node root, int min, int max)

B. public boolean isBST(Node root, int min, int max)

C. public void isBST(Node root)

D. public boolean isBST(Node root, Node min, Node max)

Solution

1. Step 1: Identify correct return type and parameters

   Checking BST returns true/false, so return type should be boolean. Also, min and max values are needed as integers to validate node values.

2. Step 2: Match method signature

   public boolean isBST(Node root, int min, int max) matches this: boolean return type and int min, max parameters. Others have wrong return types or parameter types.

3. Final Answer:

   public boolean isBST(Node root, int min, int max) -> Option B

4. Quick Check:

   Return boolean with int min/max params [OK]

Hint: Use boolean return and int min/max for range checks [OK]

Common Mistakes:

• Using void return type for a check method
• Using Node type for min/max instead of int
• Returning int instead of boolean

3. What will be the output of the following code snippet?

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

public class Test {
  static boolean isBST(Node root, int min, int max) {
    if (root == null) return true;
    if (root.val <= min || root.val >= max) return false;
    return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
  }

  public static void main(String[] args) {
    Node root = new Node(10);
    root.left = new Node(5);
    root.right = new Node(15);
    root.left.left = new Node(1);
    root.left.right = new Node(12);
    System.out.println(isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
  }
}

medium

A. Runtime exception

B. true

C. Compilation error

D. false

Solution

1. Step 1: Trace the tree nodes and BST conditions

   The node with value 12 is in the left subtree of 10 but greater than 10, violating BST property.

2. Step 2: Check isBST calls

   When checking root.left.right (12), it fails the condition root.val <= min or root.val >= max because 12 >= 10 is true, so returns false.

3. Final Answer:

   false -> Option D

4. Quick Check:

   Node 12 violates BST rule, so false [OK]

Hint: Check if any left child > root or right child < root [OK]

Common Mistakes:

• Ignoring subtree value ranges
• Assuming all nodes in left subtree are less than root only
• Not updating min/max during recursion

4. Identify the bug in this BST validation code snippet:

boolean isBST(Node root) {
  if (root == null) return true;
  if (root.left != null && root.left.val > root.val) return false;
  if (root.right != null && root.right.val < root.val) return false;
  return isBST(root.left) && isBST(root.right);
}

medium

A. It does not handle null root properly

B. It uses wrong comparison operators for left and right children

C. It does not check the entire subtree values, only immediate children

D. It should return int instead of boolean

Solution

1. Step 1: Analyze the checks performed

   The code only compares root with its immediate left and right children, not the entire subtree.

2. Step 2: Understand BST validation requirement

   BST validation requires all nodes in left subtree < root and all in right subtree > root, not just immediate children.

3. Final Answer:

   It does not check the entire subtree values, only immediate children -> Option C

4. Quick Check:

   Check full subtree ranges, not just children [OK]

Hint: Check full subtree ranges, not just direct children [OK]

Common Mistakes:

• Only comparing immediate children values
• Ignoring recursive min/max range checks
• Assuming local checks are enough

5. Given a binary tree, which approach correctly validates if it is a BST considering edge cases like duplicate values and integer limits?

hard

A. Use min and max integer range parameters updated during recursion

B. Use in-order traversal to check if values are strictly increasing

C. Check only immediate children values recursively

D. Compare each node with root only, ignoring subtrees

Solution

1. Step 1: Understand edge cases in BST validation

   Duplicates and integer limits require careful range checks, not just value comparisons.

2. Step 2: Evaluate approaches

   Using min and max parameters updated during recursion correctly enforces BST property for all nodes and handles edge cases.

3. Final Answer:

   Use min and max integer range parameters updated during recursion -> Option A

4. Quick Check:

   Range checks with min/max handle edge cases [OK]

Hint: Use min/max range checks recursively for full validation [OK]

Common Mistakes:

• Ignoring duplicates or equal values
• Not updating min/max during recursion
• Only checking immediate children