Validate if Tree is BST in DSA Python - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check if node is None?

Yes→Return True

No↓

Check node value > min and < max?

No→Return False

Yes↓

Recurse left subtree with updated max = node value

↓

Recurse right subtree with updated min = node value

↓

Return left_result AND right_result

We start at the root and check if each node's value fits the allowed min and max range. We update these bounds as we go down left and right subtrees. If all nodes satisfy the BST property, we return True.

Execution Sample

DSA Python

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))

This function checks if a binary tree is a BST by verifying node values within min and max bounds recursively.

Execution Table

Step	Operation	Node Visited	Min Bound	Max Bound	Result	Tree State
1	Start at root	10	-inf	inf	Check 10 in (-inf, inf)	10 / \ 5 15
2	Recurse left	5	-inf	10	Check 5 in (-inf, 10)	10 / \ 5 15
3	Recurse left of 5	3	-inf	5	Check 3 in (-inf, 5)	10 / \ 5 15 / 3
4	Recurse left of 3	None	-inf	3	None node, return True	10 / \ 5 15 / 3
5	Recurse right of 3	None	3	5	None node, return True	10 / \ 5 15 / 3
6	Left subtree of 3 is BST	3	-inf	5	True	10 / \ 5 15 / 3
7	Recurse right of 5	7	5	10	Check 7 in (5, 10)	10 / \ 5 15 / \ 3 7
8	Recurse left of 7	None	5	7	None node, return True	10 / \ 5 15 / \ 3 7
9	Recurse right of 7	None	7	10	None node, return True	10 / \ 5 15 / \ 3 7
10	Right subtree of 5 is BST	7	5	10	True	10 / \ 5 15 / \ 3 7
11	Left subtree of 5 is BST	5	-inf	10	True	10 / \ 5 15 / \ 3 7
12	Recurse right	15	10	inf	Check 15 in (10, inf)	10 / \ 5 15 / \ 3 7
13	Recurse left of 15	13	10	15	Check 13 in (10, 15)	10 / \ 5 15 / \ / 3 7 13
14	Recurse left of 13	None	10	13	None node, return True	10 / \ 5 15 / \ / 3 7 13
15	Recurse right of 13	None	13	15	None node, return True	10 / \ 5 15 / \ / 3 7 13
16	Left subtree of 15 is BST	13	10	15	True	10 / \ 5 15 / \ / 3 7 13
17	Recurse right of 15	20	15	inf	Check 20 in (15, inf)	10 / \ 5 15 / \ / \ 3 7 13 20
18	Recurse left of 20	None	15	20	None node, return True	10 / \ 5 15 / \ / \ 3 7 13 20
19	Recurse right of 20	None	20	inf	None node, return True	10 / \ 5 15 / \ / \ 3 7 13 20
20	Right subtree of 15 is BST	20	15	inf	True	10 / \ 5 15 / \ / \ 3 7 13 20
21	Right subtree of root is BST	15	10	inf	True	10 / \ 5 15 / \ / \ 3 7 13 20
22	Whole tree is BST	10	-inf	inf	True	10 / \ 5 15 / \ / \ 3 7 13 20

💡 All nodes satisfy BST property, recursion ends with True

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 12	After Step 17	Final
node.val	10	5	7	15	20	10
min_val	-inf	-inf	5	10	15	-inf
max_val	inf	10	10	inf	inf	inf
Result	N/A	True	True	True	True	True

Key Moments - 3 Insights

Why do we check if node.val is strictly greater than min_val and less than max_val?

Because BST requires all left subtree nodes to be less than the current node and all right subtree nodes to be greater. This strict inequality ensures no duplicates or invalid placements. See steps 3, 7, 12 where these checks happen.

What happens when we reach a None node?

Reaching None means we hit a leaf's child, which is valid and considered BST by definition. The function returns True immediately as shown in steps 4, 5, 8, 9, 14, 15, 18, 19.

Why do we update max_val when going left and min_val when going right?

Because left subtree nodes must be less than the current node, so max_val becomes current node's value. Right subtree nodes must be greater, so min_val becomes current node's value. This is shown in steps 2 (max_val=10) and 12 (min_val=10).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the min_val and max_val when visiting node 7?

A 5 and 10

B -inf and 10

C 5 and inf

D 10 and inf

💡 Hint

Check the 'Min Bound' and 'Max Bound' columns at step 7 in execution_table

At which step does the recursion check the right subtree of node 15?

A Step 13

B Step 12

C Step 17

D Step 20

💡 Hint

Look for 'Recurse right of 15' operation in execution_table

If node 13 had value 16 instead, which step would fail the BST check?

A Step 16

B Step 13

C Step 14

D Step 17

💡 Hint

Check step 13 where node 13 is checked against max_val 15

Concept Snapshot

Validate BST by recursion:
- Start at root with min=-inf, max=inf
- Check node.val in (min, max)
- Recurse left with max=node.val
- Recurse right with min=node.val
- Return True if all nodes valid
- Return False if any violation

Full Transcript

To check if a binary tree is a BST, we start at the root node. We keep track of allowed minimum and maximum values for each node. Initially, min is negative infinity and max is positive infinity. For each node, we check if its value is strictly between min and max. If not, the tree is not a BST. If yes, we recursively check the left subtree with updated max as the current node's value, and the right subtree with updated min as the current node's value. When we reach a None node, we return True because empty trees are valid BSTs. If all nodes satisfy the condition, the entire tree is a BST. The execution table shows each step visiting nodes 10, 5, 3, 7, 15, 13, and 20 with their min and max bounds and results. Key moments clarify why strict inequalities are needed, what happens at None nodes, and why bounds update differently for left and right subtrees.

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