Validate if Tree is BST in DSA Java - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check left subtree values < current node?

↓

Recursively validate left subtree

↓

Check right subtree values > current node?

↓

Recursively validate right subtree

↓

If all checks pass, return True

↓

Else return False

The validation starts at the root and recursively checks if all nodes in the left subtree are smaller and all nodes in the right subtree are larger, ensuring BST properties.

Execution Sample

DSA Java

boolean isBST(Node 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);
}

This code checks if a binary tree is a BST by ensuring each node's value is within valid min and max bounds recursively.

Execution Table

Step	Operation	Node Visited	Min Bound	Max Bound	Result	Tree State
1	Start at root	10	-∞	+∞	Continue	10 / \ 5 15
2	Check left child	5	-∞	10	Continue	10 / \ 5 15
3	Check left-left child	2	-∞	5	Continue	10 / \ 5 15 / 2
4	Left-left-left child null	null	-∞	2	True	No change
5	Left-left-right child null	null	2	5	True	No change
6	Left child 5 subtree valid	5	-∞	10	True	No change
7	Check right child	15	10	+∞	Continue	10 / \ 5 15
8	Check right-left child	12	10	15	Continue	10 / \ 5 15 / 12
9	Right-left-left child null	null	10	12	True	No change
10	Right-left-right child null	null	12	15	True	No change
11	Right-left subtree valid	12	10	15	True	No change
12	Check right-right child	20	15	+∞	Continue	10 / \ 5 15 / \ 12 20
13	Right-right-left child null	null	15	20	True	No change
14	Right-right-right child null	null	20	+∞	True	No change
15	Right child 15 subtree valid	15	10	+∞	True	No change
16	Root node 10 subtree valid	10	-∞	+∞	True	Tree is BST

💡 All nodes satisfy BST conditions, recursion ends with True

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 11	After Step 15	Final
node	10	5	5	12	15	10
min	-∞	-∞	-∞	10	10	-∞
max	+∞	10	10	15	+∞	+∞
Result	N/A	Continue	True	True	True	True

Key Moments - 3 Insights

Why do we pass min and max bounds when checking each node?

Because each node must be greater than all nodes in its left ancestors (min) and less than all nodes in its right ancestors (max). This is shown in execution_table steps 2, 7, and 12 where bounds are updated.

Why do we return true when node is null?

A null node means we reached a leaf's child, which does not violate BST rules. This is shown in steps 4, 5, 9, 10, 13, and 14 where null nodes return true.

What happens if a node value is equal to min or max?

The code returns false because BST requires strictly less or greater values. This is checked in step 3 and 8 conditions in the code.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what are the min and max bounds for node 2?

A -∞ and 5

B 5 and 10

C -∞ and 10

D 2 and 5

💡 Hint

Check the Min Bound and Max Bound columns at step 3 in execution_table

At which step does the recursion confirm the right subtree of node 15 is valid?

A Step 10

B Step 14

C Step 12

D Step 16

💡 Hint

Look for null child checks under node 20 in execution_table steps 13 and 14

If node 12 had value 16, which step would fail the BST condition?

A Step 8

B Step 7

C Step 11

D Step 15

💡 Hint

Check the condition at step 8 where node 12 must be less than max bound 15

Concept Snapshot

Validate BST by checking each node's value is within min and max bounds.
Use recursion to check left subtree with updated max and right subtree with updated min.
Return true for null nodes (leaf children).
Fail if node value not strictly between min and max.
This ensures all left nodes < current < all right nodes.

Full Transcript

To validate if a binary tree is a BST, we start at the root node and recursively check each node's value against allowed minimum and maximum bounds. Initially, these bounds are negative and positive infinity. For the left subtree, the maximum bound becomes the current node's value, and for the right subtree, the minimum bound becomes the current node's value. If a node is null, it means we've reached beyond a leaf and return true. If any node's value is not strictly between min and max, we return false. This process continues until all nodes are validated or a violation is found. The execution table shows step-by-step how nodes are visited, bounds updated, and results returned, confirming the tree is a BST.

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