Validate if Tree is BST in DSA Python - 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 at most two children. For every node, all values in its left subtree are smaller, and all values in its right subtree are larger. 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 and sorting.

Why it matters

Without knowing if a tree is a BST, we cannot trust its fast search abilities. If the tree breaks the BST rules, searching for values can become slow and inefficient, like looking for a book in a messy library. Validating a BST helps maintain data integrity and performance in many applications like databases and file systems.

Where it fits

Before this, learners should understand basic tree structures and binary trees. After this, learners can explore tree operations like insertion, deletion, and balanced BSTs such as AVL or Red-Black trees.

Mental Model

Core Idea

A tree is a BST if every node's left subtree has smaller values and right subtree has larger values, consistently throughout the tree.

Think of it like...

Imagine a family photo album organized so that all photos on the left pages are from earlier years and all photos on the right pages are from later years. If any photo is out of order, the album is not properly sorted.

        [Node]
       /      \
  [Left]    [Right]
  < Node    > Node

Every left subtree < Node < Every right subtree

Build-Up - 7 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. Example: 10 / \ 5 15 Here, 10 is the root, 5 is left child, 15 is right child.

Result

You can visualize and identify nodes and their children in a binary tree.

Understanding the basic shape and connections of a binary tree is essential before checking any ordering rules.

2

Foundation

Know BST Property Basics

Concept: Learn the rule that defines a BST: left children are smaller, right children are larger.

In a BST, for every node: - All values in the left subtree are less than the node's value. - All values in the right subtree are greater than the node's value. Example: 10 / \ 5 15 5 < 10 < 15, so this is a BST.

Result

You can identify if a small tree follows the BST property by comparing node values.

Knowing this rule is the foundation for validating any tree as a BST.

3

Intermediate

Check BST Using Inorder Traversal

🤔Before reading on: Do you think simply checking if values are sorted during inorder traversal is enough to confirm a BST? Commit to yes or no.

Concept: Use inorder traversal to visit nodes in ascending order if the tree is a BST.

Inorder traversal visits nodes in this order: left subtree, node, right subtree. If the tree is a BST, the values visited will be in strictly increasing order. Example traversal of BST: Values visited: 5, 10, 15 If values are not sorted, the tree is not a BST.

Result

You get a list of values from the tree that should be sorted if the tree is a BST.

Understanding that inorder traversal produces sorted values in a BST helps validate the tree efficiently.

4

Intermediate

Validate BST with Min-Max Limits

🤔Before reading on: Is it enough to check only immediate children values to validate BST? Commit to yes or no.

Concept: Use a recursive approach passing down allowed min and max value limits for each node.

Each node must be within a range: - Initially, root can be any value. - Left child must be less than current node. - Right child must be greater than current node. We pass these limits down the tree: Example: Node 10: min = -∞, max = +∞ Left child 5: min = -∞, max = 10 Right child 15: min = 10, max = +∞ If any node breaks these limits, tree is not BST.

Result

You can detect BST violations anywhere in the tree, not just immediate children.

Knowing to track value limits prevents missing violations deeper in the tree structure.

5

Intermediate

Implement Recursive BST Validation Code

Concept: Write a function that recursively checks each node against min and max limits.

Python example: class Node: def __init__(self, val): self.val = val self.left = None self.right = None def is_bst(node, min_val=float('-inf'), max_val=float('inf')): if node is None: return True if not (min_val < node.val < max_val): return False return (is_bst(node.left, min_val, node.val) and is_bst(node.right, node.val, max_val)) # Example tree root = Node(10) root.left = Node(5) root.right = Node(15) print(is_bst(root)) # Output: True

Result

The function returns True if the tree is a BST, False otherwise.

Implementing this recursive check solidifies understanding of BST validation logic.

6

Advanced

Detect BST Violations Beyond Immediate Children

🤔Before reading on: Can a tree fail BST validation even if every parent-child pair looks correct? Commit to yes or no.

Concept: Understand that violations can occur deeper in subtrees, not just between parent and child nodes.

Example: 10 / \ 5 15 / 6 Here, 6 is left child of 15, which is correct locally (6 < 15), but 6 < 10 violates BST rules because 6 is in right subtree of 10. Simple parent-child checks miss this violation. Using min-max limits catches this because 6 must be > 10 to be in right subtree.

Result

You learn that BST validation must consider entire subtree ranges, not just immediate nodes.

Understanding this prevents subtle bugs in BST validation that can cause incorrect results.

7

Expert

Optimize BST Validation with Inorder State Tracking

🤔Before reading on: Is it possible to validate BST without extra space for storing all values? Commit to yes or no.

Concept: Use inorder traversal with a variable tracking the last visited node value to check sorted order on the fly.

Instead of storing all values, keep track of the last visited node's value during inorder traversal. If current node's value is not greater than last visited, tree is not BST. Example code snippet: last_val = float('-inf') def is_bst_inorder(node): nonlocal last_val if node is None: return True if not is_bst_inorder(node.left): return False if node.val <= last_val: return False last_val = node.val return is_bst_inorder(node.right) This method uses O(h) space where h is tree height, better than storing all values.

Result

You can validate BST efficiently without extra memory for full traversal results.

Knowing this optimization helps write memory-efficient BST validation suitable for large trees.

Under the Hood

BST validation works by ensuring every node's value fits within a valid range defined by its ancestors. The recursive checks propagate these min and max limits down the tree. Internally, the algorithm visits each node once, comparing its value to these limits, which guarantees O(n) time complexity. The inorder traversal method relies on the property that BST nodes visited in order produce a sorted sequence, so checking sortedness confirms the BST property.

Why designed this way?

The min-max approach was designed to catch violations anywhere in the tree, not just between parent and child nodes. Early methods that checked only immediate children failed on deeper violations. The inorder traversal method leverages the natural sorted order of BSTs to simplify validation. Both methods balance correctness and efficiency, avoiding unnecessary repeated checks.

          [Root Node]
          /         \
   [Left Subtree]  [Right Subtree]
      min < val < max

Recursive calls pass down updated min and max:

Left child: min ... val
Right child: val ... max

Each node checked against these limits.

Myth Busters - 3 Common Misconceptions

Quick: Is checking only parent and immediate children enough to confirm BST? Commit yes or no.

Common Belief: If every parent node is greater than its left child and less than its right child, the tree is a BST.

Reality: This is false because violations can occur deeper in subtrees where a node breaks the BST property relative to an ancestor, not just its parent.

Why it matters: Relying on this leads to false positives, causing incorrect assumptions about tree order and potentially breaking search operations.

Quick: Does inorder traversal always produce sorted values for any binary tree? Commit yes or no.

Common Belief: Inorder traversal always gives sorted values, so if values are sorted, the tree is a BST.

Reality: Inorder traversal only produces sorted values if the tree is a BST. For other trees, values may not be sorted.

Why it matters: Misunderstanding this can cause confusion when inorder traversal results are not sorted, leading to wrong conclusions.

Quick: Can a BST contain duplicate values? Commit yes or no.

Common Belief: BSTs can have duplicate values anywhere in the tree.

Reality: Standard BSTs do not allow duplicates or require a strict ordering rule (e.g., duplicates only on one side). Allowing duplicates without rules breaks BST properties.

Why it matters: Ignoring this can cause validation errors or inconsistent tree behavior in searching and insertion.

Expert Zone

1

BST validation must consider strict inequalities to avoid duplicates breaking the tree's search guarantees.

2

The min-max recursive method is more general and can be adapted for trees with custom ordering rules or augmented data.

3

Inorder traversal validation can be combined with iterative traversal to reduce call stack overhead in deep trees.

When NOT to use

Avoid using simple parent-child comparisons for BST validation as they miss deep violations. For trees allowing duplicates, use specialized validation rules. For very large or unbalanced trees, consider iterative inorder traversal to avoid stack overflow.

Production Patterns

In real systems, BST validation is used during tree construction, balancing, and debugging. Database indexes and file systems use similar validation to ensure data integrity. Optimized iterative or tail-recursive methods are preferred for performance and memory efficiency.

Connections

Binary Tree Traversals

Builds-on

Understanding inorder traversal is key to validating BSTs because it reveals the sorted order property unique to BSTs.

Range Checking in Algorithms

Same pattern

The min-max validation approach is a form of range checking, a common pattern in algorithms to enforce constraints across recursive calls.

Quality Control in Manufacturing

Analogous process

Validating a BST is like quality control checking every part of a product against strict standards to ensure overall integrity.

Common Pitfalls

#1 Checking only immediate children values for BST validation.

Wrong approach:

def is_bst_simple(node):
if node is None:
return True
if node.left and node.left.val >= node.val:
return False
if node.right and node.right.val <= node.val:
return False
return is_bst_simple(node.left) and is_bst_simple(node.right)

Correct approach:

def is_bst(node, min_val=float('-inf'), max_val=float('inf')):
if node is None:
return True
if not (min_val < node.val < max_val):
return False
return is_bst(node.left, min_val, node.val) and is_bst(node.right, node.val, max_val)

Root cause:

Misunderstanding that BST property applies to entire subtrees, not just direct children.

#2 Using inorder traversal but not checking for strict increasing order.

Wrong approach:

def is_bst_inorder_wrong(node):
values = []
def inorder(n):
if n:
inorder(n.left)
values.append(n.val)
inorder(n.right)
inorder(node)
return values == sorted(values)

Correct approach:

last_val = float('-inf')

def is_bst_inorder(node):
nonlocal last_val
if node is None:
return True
if not is_bst_inorder(node.left):
return False
if node.val <= last_val:
return False
last_val = node.val
return is_bst_inorder(node.right)

Root cause:

Not enforcing strict inequality allows duplicates or equal values to pass incorrectly.

Key Takeaways

A BST requires every node's left subtree to have smaller values and right subtree to have larger values, not just immediate children.

Validating a BST can be done efficiently using recursive min-max limits or inorder traversal checking sorted order.

Simple parent-child comparisons are insufficient and can miss violations deeper in the tree.

Inorder traversal of a BST produces values in strictly increasing order, which is a key property for validation.

Optimized validation methods reduce memory use and improve performance, important for large or deep trees.

Practice

1. What does it mean for a binary tree to be a Binary Search Tree (BST)?

easy

A. The tree is balanced with equal height on both sides.

B. Every node has exactly two children.

C. All nodes have the same value.

D. Every node's left subtree contains values less than the node, and right subtree contains values greater.

Solution

1. Step 1: Understand BST property

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

2. Step 2: Compare options with definition

   Every node's left subtree contains values less than the node, and right subtree contains values greater. matches this property exactly, while others describe different tree properties.

3. Final Answer:

   Every node's left subtree contains values less than the node, and right subtree contains values greater. -> Option D

4. Quick Check:

   BST property = Every node's left subtree contains values less than the node, and right subtree contains values greater. [OK]

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

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Assuming all values are equal

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

easy

A. def is_bst(root):

B. def validateBST(root, min_val, max_val):

C. def checkBST(tree):

D. def bst_check():

Solution

1. Step 1: Identify typical BST validation parameters

   To validate BST, we usually pass the node and the allowed min and max value range to check subtree values.

2. Step 2: Match function signatures

   def validateBST(root, min_val, max_val): includes root, min_val, and max_val parameters, which is the standard approach for BST validation.

3. Final Answer:

   def validateBST(root, min_val, max_val): -> Option B

4. Quick Check:

   Function with min and max parameters = def validateBST(root, min_val, max_val): [OK]

Hint: BST check needs min and max limits [OK]

Common Mistakes:

• Using no parameters or wrong parameters
• Missing min and max value checks
• Incorrect function naming causing confusion

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

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def is_bst(node, min_val=float('-inf'), max_val=float('inf')):
    if not node:
        return True
    if not (min_val < node.val < max_val):
        return False
    return (is_bst(node.left, min_val, node.val) and
            is_bst(node.right, node.val, max_val))

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(1)
root.left.right = Node(12)
print(is_bst(root))

medium

A. Error

B. True

C. False

D. None

Solution

1. Step 1: Trace the tree structure and BST property

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

2. Step 2: Check the is_bst function logic

   The function returns False because 12 is not less than 10 (max_val for left subtree), so the condition fails.

3. Final Answer:

   False -> Option C

4. Quick Check:

   Left subtree value > root = False [OK]

Hint: Check if left subtree values < node [OK]

Common Mistakes:

• Ignoring subtree value ranges
• Assuming all left children are smaller without checking ancestors
• Confusing node values with their immediate parent only

4. Find the bug in the following BST validation function:

def is_bst(node, min_val=None, max_val=None):
    if node is None:
        return True
    if min_val and node.val <= min_val:
        return False
    if max_val and node.val >= max_val:
        return False
    return is_bst(node.left, min_val, node.val) and is_bst(node.right, node.val, max_val)

medium

A. Using 'if min_val' causes incorrect checks when min_val is 0 or negative.

B. The function does not check if node is None.

C. The function should return False when node is None.

D. The recursive calls have wrong parameter order.

Solution

1. Step 1: Analyze condition checks for min_val and max_val

   Using 'if min_val' fails when min_val is 0 or negative because 0 is False in Python.

2. Step 2: Identify correct way to check None

   We should check 'if min_val is not None' to correctly handle 0 or negative values.

3. Final Answer:

   Using 'if min_val' causes incorrect checks when min_val is 0 or negative. -> Option A

4. Quick Check:

   Check None explicitly, not truthiness [OK]

Hint: Use 'is not None' to check min_val and max_val [OK]

Common Mistakes:

• Using truthy checks for numeric bounds
• Ignoring zero or negative values in conditions
• Misordering recursive parameters

5. Given a binary tree where nodes can have duplicate values, which modification to the BST validation logic allows duplicates only on the right subtree?

def is_bst_with_duplicates(node, min_val=float('-inf'), max_val=float('inf')):
    if not node:
        return True
    # Fill condition here
    return (is_bst_with_duplicates(node.left, min_val, node.val) and
            is_bst_with_duplicates(node.right, node.val, max_val))

hard

A. Change condition to: if not (min_val <= node.val < max_val): return False

B. Change condition to: if not (min_val <= node.val <= max_val): return False

C. Change condition to: if not (min_val < node.val < max_val): return False

D. Change condition to: if not (min_val < node.val <= max_val): return False

Solution

1. Step 1: Understand duplicate placement rule

   Duplicates allowed only on right means left subtree values must be strictly less than node.val, right subtree values can be equal or greater.

2. Step 2: Adjust inequality conditions accordingly

   Left subtree uses min_val <= node.val < max_val, so node.val can be equal to min_val but less than max_val. For right subtree, node.val can be equal to min_val.

3. Final Answer:

   Change condition to: if not (min_val <= node.val < max_val): return False -> Option A

4. Quick Check:

   Duplicates on right: allow equality on right side [OK]

Hint: Allow equality only on right subtree values [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Using strict inequalities on both sides
• Not adjusting min_val and max_val checks