Validate if Tree is BST in DSA Java - Deep Dive

Overview - Validate if Tree is BST

What is it?

A Binary Search Tree (BST) is a special kind of tree where each node has a value greater than all values in its left subtree and less than all values in its right subtree. Validating if a tree is a BST means checking if this rule holds true for every node in the tree. This helps ensure the tree can be used for fast searching, insertion, and deletion. Without this validation, the tree might not behave like a BST and could cause errors or slow operations.

Why it matters

Validating a tree as a BST is crucial because many algorithms rely on the BST property to work efficiently. If a tree is not a BST but is treated like one, searches might fail or take much longer. Imagine trying to find a book in a library where books are not sorted properly; it would be slow and frustrating. Similarly, without validation, programs can produce wrong results or crash.

Where it fits

Before learning this, you should understand what a binary tree is and basic tree traversal methods like in-order traversal. After mastering BST validation, you can learn about BST operations like insertion, deletion, and balancing techniques such as AVL or Red-Black trees.

Mental Model

Core Idea

A tree is a BST if every node's value is greater than all values in its left subtree and less than all values in its right subtree.

Think of it like...

Think of a BST like a sorted bookshelf where every book on the left shelf has a smaller number than the book in the middle, and every book on the right shelf has a bigger number. To check if the bookshelf is sorted correctly, you look at each book and make sure this rule holds everywhere.

          [Node]
         /      \
    [Left]      [Right]
   (values <)  (values >)

In-order traversal visits nodes in ascending order if it's a BST:
Left subtree -> Node -> Right subtree

Example:
      10
     /  \
    5    15
   / \     \
  2   7     20

In-order output: 2 -> 5 -> 7 -> 10 -> 15 -> 20

Build-Up - 6 Steps

1

Foundation

Understand Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value. The tree starts from a root node and branches down. For example, a node with value 10 might have a left child 5 and right child 15.

Result

You can visualize and represent trees with nodes and links to left and right children.

Understanding the basic tree structure is essential before checking any special properties like BST rules.

2

Foundation

Learn In-Order Tree Traversal

Concept: In-order traversal visits nodes in left-root-right order, which produces sorted values for BSTs.

To traverse a tree in-order, first visit the left subtree, then the current node, then the right subtree. For example, for the tree: 10 / \ 5 15 In-order traversal visits 5, then 10, then 15.

Result

In-order traversal of a BST outputs values in ascending order.

Knowing in-order traversal helps us check if the tree's values come out sorted, a key sign of a BST.

3

Intermediate

Check BST by In-Order Traversal

🤔Before reading on: do you think just checking if in-order traversal is sorted is enough to confirm a BST? Commit to yes or no.

Concept: Use in-order traversal to collect values and verify if they are strictly increasing.

Perform in-order traversal and store values in a list. Then check if each value is greater than the previous one. If yes, the tree is a BST; if not, it isn't. Example: For values [2, 5, 7, 10, 15, 20], all are increasing, so it's a BST. Java snippet: List values = new ArrayList<>(); void inorder(TreeNode node) { if (node == null) return; inorder(node.left); values.add(node.val); inorder(node.right); } boolean isBST() { for (int i = 1; i < values.size(); i++) { if (values.get(i) <= values.get(i - 1)) return false; } return true; }

Result

If the list is sorted strictly increasing, the tree is a BST; otherwise, it is not.

This method leverages the BST property that in-order traversal yields sorted values, making validation straightforward.

4

Intermediate

Validate BST Using Min-Max Limits

🤔Before reading on: do you think checking only immediate children is enough to validate BST? Commit to yes or no.

Concept: Check each node's value against allowed minimum and maximum limits passed down from ancestors.

Instead of collecting values, recursively check each node: - The node's value must be greater than a min limit and less than a max limit. - For the left child, max limit becomes the current node's value. - For the right child, min limit becomes the current node's value. Java example: boolean validate(TreeNode node, Integer min, Integer max) { if (node == null) return true; if ((min != null && node.val <= min) || (max != null && node.val >= max)) return false; return validate(node.left, min, node.val) && validate(node.right, node.val, max); }

Result

The tree is a BST only if all nodes respect their min and max constraints.

This method checks the BST property at every node with context, catching violations that simple in-order checks might miss.

5

Advanced

Detect BST Violations in Complex Trees

🤔Before reading on: can a tree fail BST validation even if all parent-child pairs look correct? Commit to yes or no.

Concept: Understand that BST violations can occur deep in subtrees, not just between immediate parent and child.

Consider this tree: 10 / \ 5 15 / \ 6 20 Here, 6 is in the right subtree of 10 but less than 10, violating BST rules. The min-max method detects this because 6 must be >10 but it is not. Simple parent-child checks would miss this violation.

Result

The tree is NOT a BST because 6 violates the BST property deep in the right subtree.

Knowing that BST violations can be subtle prevents false positives and ensures robust validation.

6

Expert

Optimize BST Validation with O(1) Space

🤔Before reading on: do you think it's possible to validate BST without extra space for storing values? Commit to yes or no.

Concept: Use in-order traversal with a variable to track the previous node's value, avoiding extra list storage.

Instead of storing all values, keep track of the last visited node's value during in-order traversal. Java example: Integer prev = null; boolean validate(TreeNode node) { if (node == null) return true; if (!validate(node.left)) return false; if (prev != null && node.val <= prev) return false; prev = node.val; return validate(node.right); } This method uses recursion stack but no extra list, saving memory.

Result

BST validation completes with O(n) time and O(h) space, where h is tree height, without extra arrays.

Understanding this optimization helps write memory-efficient code suitable for large trees.

Under the Hood

BST validation works by ensuring the ordering property holds at every node. The min-max approach passes down constraints from ancestors to children, effectively narrowing the allowed range for each node's value. The in-order traversal method relies on the fact that visiting nodes in left-root-right order of a BST produces sorted values. Internally, recursion manages traversal and constraint checks, and the call stack keeps track of the path.

Why designed this way?

The min-max method was designed to catch violations that simple parent-child checks miss, especially in complex trees. In-order traversal validation is intuitive and leverages the sorted nature of BSTs. Both methods balance clarity and efficiency. Alternatives like checking only immediate children are simpler but incorrect. The min-max approach was chosen for correctness and ease of implementation.

BST Validation Flow:

[Start at Root]
      |
      v
[Check Node Value]
  /           \
Yes            No
/               \
[Recurse Left]  [Fail]
  |
  v
[Recurse Right]
  |
  v
[All Nodes Valid?]
  /          \
Yes           No
/              \
[Return True]  [Return False]

Myth Busters - 3 Common Misconceptions

Quick: Do you think checking only if left child < node and right child > node is enough to confirm BST? Commit to yes or no.

Common Belief: If every node's left child is smaller and right child is bigger, the tree must be a BST.

Reality: This is false because violations can occur deeper in subtrees, not just immediate children.

Why it matters: Relying on this leads to false positives, causing incorrect assumptions about tree order and breaking algorithms that depend on BST properties.

Quick: Do you think in-order traversal always produces sorted values for any binary tree? Commit to yes or no.

Common Belief: In-order traversal output is always sorted, so it can confirm BST.

Reality: Only BSTs produce sorted in-order traversal; other binary trees do not guarantee sorted output.

Why it matters: Assuming sorted output without BST property can cause wrong validation and bugs in tree-based algorithms.

Quick: Do you think BST validation requires checking every node's value against all ancestors? Commit to yes or no.

Common Belief: You must compare each node to all its ancestors to validate BST.

Reality: The min-max method efficiently passes down constraints, so you only check current node against min and max limits, not all ancestors individually.

Why it matters: Understanding this prevents inefficient code and helps write clean, fast validation functions.

Expert Zone

1

The min-max validation method elegantly handles duplicate values by defining strict inequalities, which some BST definitions allow or disallow.

2

In-order traversal validation can be combined with iterative traversal to avoid recursion stack overflow in very deep trees.

3

BST validation can be extended to augmented BSTs (like interval trees) by adjusting constraints, a subtlety often missed.

When NOT to use

If the tree is very large and memory is limited, recursive methods might cause stack overflow; iterative traversal or Morris traversal can be better. Also, if the tree allows duplicates with special rules, standard BST validation must be adapted. For non-binary trees or balanced trees like AVL, additional properties must be checked beyond BST validation.

Production Patterns

In real systems, BST validation is used during tree construction, debugging, and before performing operations like search or delete. It is often combined with balancing checks in self-balancing trees. Validation code is optimized for performance and memory, sometimes using iterative traversal or early exit on failure.

Connections

In-Order Tree Traversal

Builds-on

Understanding in-order traversal is key to grasping why BST validation can be done by checking sorted order of visited nodes.

Binary Tree

Prerequisite

Knowing binary tree structure is essential before learning BST validation, as BST is a special kind of binary tree.

Sorting Algorithms

Related pattern

BST validation via in-order traversal relates to sorting because it checks if tree values come out sorted, linking tree structure to order concepts in sorting.

Common Pitfalls

#1 Checking only immediate children for BST property.

Wrong approach:

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

Correct approach:

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

Root cause:

Misunderstanding that BST property applies globally, not just between parent and immediate children.

#2 Using in-order traversal but not checking for strictly increasing order.

Wrong approach:

List values = new ArrayList<>();
void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
values.add(node.val);
inorder(node.right);
}

boolean isBST() {
for (int i = 1; i < values.size(); i++) {
if (values.get(i) < values.get(i - 1)) return false; // allows equal values
}
return true;
}

Correct approach:

for (int i = 1; i < values.size(); i++) {
if (values.get(i) <= values.get(i - 1)) return false; // strict inequality
}

Root cause:

Not enforcing strict ordering allows duplicates or equal values, violating BST rules.

#3 Not resetting previous value when using in-order traversal validation recursively.

Wrong approach:

Integer prev = null;
boolean validate(TreeNode node) {
if (node == null) return true;
if (!validate(node.left)) return false;
if (prev != null && node.val <= prev) return false;
// Missing prev = node.val assignment here
return validate(node.right);
}

Correct approach:

Integer prev = null;
boolean validate(TreeNode node) {
if (node == null) return true;
if (!validate(node.left)) return false;
if (prev != null && node.val <= prev) return false;
prev = node.val;
return validate(node.right);
}

Root cause:

Forgetting to update the previous value breaks the validation logic.

Key Takeaways

A Binary Search Tree requires every node's left subtree to have smaller values and right subtree to have larger values.

In-order traversal of a BST produces values in strictly increasing order, which can be used to validate the tree.

The min-max method validates BST by passing down value constraints to each node, catching subtle violations.

Simple checks of immediate children are not enough; global constraints must be enforced for correct validation.

Optimized validation can be done with O(1) extra space by tracking the previous node's value during traversal.

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