Validate Binary Search Tree

📋

Problem

Imagine you are building a database index that relies on a binary search tree structure. You need to verify if the tree is correctly structured to ensure fast lookups.

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: - The left subtree of a node contains only nodes with keys less than the node's key. - The right subtree of a node contains only nodes with keys greater than the node's key. - Both the left and right subtrees must also be binary search trees. Input: root node of a binary tree. Output: true if the tree is a valid BST, false otherwise.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be negative or positive.You must solve the problem with O(n) time complexity.

Edge cases: Single node tree → trueTree with duplicate values → false (BST requires strictly less/greater)Left skewed tree (all nodes have only left child) → true if values strictly decreasing

</>

IDE

def is_valid_bst(root: Optional[TreeNode]) -> bool:public boolean isValidBST(TreeNode root)bool isValidBST(TreeNode* root)function isValidBST(root)

def is_valid_bst(root):
    # Write your solution here
    pass

class Solution {
    public boolean isValidBST(TreeNode root) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isValidBST(TreeNode* root) {
    // Write your solution here
    return false;
}

function isValidBST(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueCode only compares immediate children to parent, missing violations deeper in subtrees.✅ Use recursive min/max bounds to validate all descendants, not just direct children.

Wrong: trueCode allows duplicate values by using <= or >= instead of strict < and > comparisons.✅ Change comparisons to strict inequalities: left < node < right.

Wrong: falseCode fails on single node trees due to missing base case or null pointer errors.✅ Return true immediately for null or leaf nodes.

Wrong: TLECode uses O(n^2) brute force approach checking subtree min/max repeatedly.✅ Implement O(n) solution using min/max range validation or inorder traversal.

✓

Test Cases

Try testing your solution on minimal trees and trees with duplicates to catch base case bugs.

Think about how to detect violations not just at immediate children but anywhere in the subtree.

Optimize your solution to run in linear time by avoiding repeated subtree traversals.

t1_01basic

Input{"root":[2,1,3]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The tree: 2 / \ 1 3 All left nodes are less than 2 and all right nodes are greater than 2.

💡 Recall the BST property: left < node < right for all nodes.

💡 Use a recursive helper with min and max bounds to validate each node.

💡 Check that each node's value is strictly between allowed min and max ranges.

Why it failed: Failed basic test: likely did not enforce strict inequality or min/max bounds correctly. Fix by passing updated min/max limits in recursion.

✓ Correctly validates BST property using min/max bounds.

t1_02basic

Input{"root":[5,1,7,null,null,6,8]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The tree: 5 / \ 1 7 / \ 6 8 All left nodes less than 5, right nodes greater than 5, and subtrees valid BSTs.

💡 Check each subtree recursively with updated min/max constraints.

💡 Remember to update bounds when moving left or right in the tree.

💡 Ensure no node violates the BST property by being outside its allowed range.

Why it failed: Failed to update min/max bounds properly when recursing into subtrees. Fix by passing correct bounds for left and right children.

✓ Properly maintains and checks min/max bounds for all nodes.

t2_01edge

Input{"root":[1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single node tree is always a valid BST.

💡 A single node with no children trivially satisfies BST conditions.

💡 Check that your code handles leaf nodes correctly without errors.

💡 Return true immediately if node has no children.

Why it failed: Code fails on single node trees, possibly due to null pointer or missing base case. Fix by returning true when node is leaf or null.

✓ Handles single node trees correctly.

t2_02edge

Input{"root":[2,2,2]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tree with duplicate values violates strict BST property (left < node < right).

💡 BST requires strict inequality, not <= or >=.

💡 Check that your comparisons use < and >, not <= or >=.

💡 Fix comparisons to enforce strict less than for left and greater than for right.

Why it failed: Code incorrectly allows duplicates by using <= or >= instead of < and >. Fix by changing comparisons to strict inequalities.

✓ Correctly rejects trees with duplicate values.

t2_03edge

Input{"root":[3,2,null,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Left skewed tree with strictly decreasing values: 3 -> 2 -> 1 is a valid BST.

💡 Check that left children are strictly less than their parent nodes.

💡 Ensure recursion correctly handles skewed trees with null right children.

💡 Verify min/max bounds propagate correctly down the left chain.

Why it failed: Code fails on skewed trees due to incorrect null handling or bounds propagation. Fix by properly handling null children and updating bounds.

✓ Correctly validates left skewed BSTs.

t3_01corner

Input{"root":[10,5,15,null,null,6,20]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Right subtree has a node (6) less than root (10), violating BST property.

💡 BST property must hold for all descendants, not just immediate children.

💡 Use min/max bounds to check entire subtree ranges, not just direct children.

💡 Fix by passing down min/max limits and validating all nodes against them.

Why it failed: Code only compares immediate children to parent, missing deeper violations. Fix by enforcing min/max bounds recursively for all descendants.

✓ Correctly detects violations deep in subtrees.

t3_02corner

Input{"root":[1,null,1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Right child equals root value, violating strict greater-than rule.

💡 BST requires right child values strictly greater than parent.

💡 Check that your code uses > for right child comparisons, not >=.

💡 Fix comparisons to enforce strict inequality for right subtree.

Why it failed: Code allows equal values on right subtree by using >= instead of >. Fix by changing to strict > comparison.

✓ Correctly rejects equal values on right subtree.

t3_03corner

Input{"root":[5,4,6,null,null,3,7]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Node with value 3 in right subtree of 5 is less than 5, violating BST property.

💡 BST property applies to all descendants, not just immediate children.

💡 Use min/max bounds to validate all nodes in subtrees.

💡 Fix by passing updated bounds and checking all nodes against them.

Why it failed: Code only checks immediate children, missing violations deeper in subtree. Fix by enforcing min/max bounds recursively.

✓ Detects violations in deeper subtree nodes.

t4_01performance

Input{"root":[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Right skewed tree with n=100 nodes, strictly increasing values. O(n) time complexity required to pass within 2 seconds.

💡 Use O(n) time complexity algorithms like inorder traversal or min/max range validation.

💡 Avoid O(n^2) brute force approaches that check subtree min/max repeatedly.

💡 Implement recursive validation passing down min/max bounds or use inorder traversal.

Why it failed: TLE due to O(n^2) brute force approach checking subtree min/max repeatedly. Fix by using O(n) min/max range or inorder traversal validation.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following code snippet implementing the optimal iterative approach to convert a BST to a Greater Tree. Given the BST with nodes [2, 1, 3], what is the value of the root node after the function completes?

easy

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Trace reverse inorder traversal order

   Nodes visited in order: 3, 2, 1.

2. Step 2: Accumulate sums and update nodes

   acc_sum=0 initially. - Visit 3: acc_sum=3, node.val=3 - Visit 2: acc_sum=3+2=5, node.val=5 - Visit 1: acc_sum=5+1=6, node.val=6 Root node was 2, updated to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root node value after update is 5 [OK]

Hint: Reverse inorder sums nodes from largest to smallest [OK]

Common Mistakes:

• Confusing traversal order and updating nodes too early
• Off-by-one errors in accumulating sums
• Misidentifying which node is root after updates

2. Consider the following code for finding the lowest common ancestor in a BST. Given the BST below and nodes p=2 and q=8, what value does the function return? BST structure: 6 / \ 2 8 / \ \ 0 4 9 / \ 3 5

easy

A. 2

B. 8

C. 4

D. 6

Solution

1. Step 1: Trace first iteration with current=6

   p=2 and q=8; 2 < 6 and 8 > 6, so current is split point; return 6.

2. Step 2: Confirm no further traversal

   Since p and q lie on different sides of 6, 6 is the LCA.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Split point found at root 6 immediately [OK]

Hint: LCA is where paths to p and q diverge [OK]

Common Mistakes:

• Returning smaller node instead of split point
• Confusing left/right subtree traversal
• Off-by-one error in loop conditions

3. Consider the following code snippet for searching a value in a BST. What will be printed when searching for the value 3 in the given tree?

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

def searchBST(root, val):
    current = root
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return None

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 3)
print(result.val if result else 'null')

easy

A. 2

B. 7

C. null

D. 3

Solution

1. Step 1: Trace the search path

   Start at root (4). Since 3 < 4, move to left child (2). Since 3 > 2, move to right child (3).

2. Step 2: Check node value

   Current node value is 3, which matches the search value, so return this node.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Search follows BST property correctly and finds node with value 3 [OK]

Hint: Follow BST property to move left or right [OK]

Common Mistakes:

• Returning wrong node value due to off-by-one traversal

4. The following code attempts to recover a BST with two swapped nodes using Morris traversal. Identify the line containing the subtle bug that causes incorrect recovery when the swapped nodes are adjacent in inorder traversal.

def recoverTree(root):
    first = second = prev = None
    current = root
    while current:
        if not current.left:
            if prev and prev.val > current.val:
                if not first:
                    first = prev
                    second = current
                else:
                    second = current
            prev = current
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                pred.right = current
                current = current.left
            else:
                pred.right = None
                if prev and prev.val > current.val:
                    if not first:
                        first = prev
                        second = current
                    else:
                        second = current
                prev = current
                current = current.right
    first.val, second.val = second.val, first.val

medium

A. Swapping values at the end without checking if both nodes are found

B. Line setting second = current inside the first if condition

C. Line setting first = prev inside the second if condition

D. Line setting first = prev inside the first if condition

Solution

1. Step 1: Analyze detection of swapped nodes

   The code sets first and second whenever a violation is found, but overwrites them without preserving the first violation's first node.

2. Step 2: Identify the bug in swapping

   The swap at the end assumes both first and second are found, but if only one violation is detected (adjacent nodes swapped), second may be incorrect or null, causing wrong swap.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping without confirming both nodes leads to incorrect recovery in adjacent swaps [OK]

Hint: Must confirm both nodes before swapping values [OK]

Common Mistakes:

• Overwriting first and second on multiple violations
• Swapping values prematurely after first violation
• Not restoring tree structure after Morris traversal

5. Suppose the BST can contain negative values and duplicates, and you want to convert it to a Greater Tree where each node's new value is the sum of all nodes with values greater than or equal to it. Which modification to the optimal iterative approach is necessary to handle duplicates correctly?

hard

A. Change traversal to inorder (left-root-right) to process duplicates in ascending order.

B. Use a hash map to store counts of each value and update nodes after traversal.

C. Skip nodes with duplicate values during traversal to avoid double counting.

D. During traversal, accumulate sum including nodes with values equal to current node before updating node value.

Solution

1. Step 1: Understand how duplicates affect sum accumulation

   Duplicates must be included in the sum for nodes with equal values to maintain correctness.

2. Step 2: Modify accumulation logic

   Accumulate sum including all nodes with values >= current node before updating node.val during reverse inorder traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Including equal values in sum ensures correct Greater Tree with duplicates [OK]

Hint: Include equal values in sum during reverse inorder traversal [OK]

Common Mistakes:

• Changing traversal order breaks sum logic
• Skipping duplicates causes incorrect sums
• Using extra data structures unnecessarily increases complexity