Validate if Tree is BST in DSA Python

Mental Model

A binary search tree (BST) has nodes arranged so that left children are smaller and right children are bigger than the parent node.

Analogy: Think of a family tree where every child on the left side is younger than their parent, and every child on the right side is older, keeping the order clear.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

Input: Tree: 5 with left child 3 and right child 7; 3 has children 2 and 4; 7 has right child 8

Goal: Check if this tree follows BST rules where left < parent < right for every node

Step 1: Start at root node 5, set allowed range as (-∞, +∞)

Node=5, range=(-∞, +∞)

Why: We begin with no limits for the root node

Step 2: Check left child 3 with range (-∞, 5)

Node=3, range=(-∞, 5)

Why: Left child must be less than parent 5

Step 3: Check left child 2 of 3 with range (-∞, 3)

Node=2, range=(-∞, 3)

Why: Left child of 3 must be less than 3

Step 4: Check right child 4 of 3 with range (3, 5)

Node=4, range=(3, 5)

Why: Right child of 3 must be greater than 3 but less than 5

Step 5: Check right child 7 of 5 with range (5, +∞)

Node=7, range=(5, +∞)

Why: Right child must be greater than parent 5

Step 6: Check right child 8 of 7 with range (7, +∞)

Node=8, range=(7, +∞)

Why: Right child of 7 must be greater than 7

Result:

Tree is a valid BST because all nodes fit their allowed ranges

Annotated Code

DSA Python

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

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

# Driver code to build the example tree
root = Node(5)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(4)
root.right.right = Node(8)

print("Is the tree a BST?", is_bst(root))

if node is None: return True

Base case: empty subtree is valid BST

if not (low < node.val < high): return False

Check if current node value fits allowed range

return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)

Recursively check left subtree with updated upper bound and right subtree with updated lower bound

Output

Is the tree a BST? True

Complexity Analysis

Time: O(n) because we visit each node once to check its value

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to checking BST by in-order traversal and verifying sorted order, this method checks constraints directly during traversal, avoiding extra storage

Edge Cases

Empty tree

Returns True since empty tree is a valid BST

DSA Python

if node is None:
    return True

Single node tree

Returns True as single node satisfies BST rules

DSA Python

if node is None:
    return True

Tree with duplicate values

Returns False because BST requires strictly less or greater values

DSA Python

if not (low < node.val < high):
    return False

When to Use This Pattern

When you need to verify if a binary tree follows ordering rules for all nodes, use the BST validation pattern with range limits to check each node's value.

Common Mistakes

Mistake: Only checking immediate children without considering the full allowed range
Fix: Pass down updated low and high limits to children to ensure all ancestors' constraints are respected

Summary

Checks if a binary tree follows BST rules by verifying node values within allowed ranges.

Use when you want to confirm a tree is a valid BST before performing BST-specific operations.

The key is to track and update the allowed value range for each node during traversal.

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