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 BSTIterator implementation using Morris traversal:

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    pre.right = None
                    self.next_val = self.current.val
                    self.current = self.current.right

Given the BST with nodes 2 (root), 1 (left child), and 3 (right child), what is the value of next_val after the first call to _advance() during initialization?

easy

A. 3

B. 2

C. 1

D. null

Solution

1. Step 1: Trace _advance() starting at root=2

   Since root has a left child (1), find predecessor of 2 in left subtree: node 1 has no right child, so set 1.right = 2 and move current to 1.

2. Step 2: At current=1, no left child, so set next_val=1 and move current to 1.right which points back to 2 (thread).

   Return from _advance() with next_val=1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   First inorder element is 1, matches next_val after first advance [OK]

Hint: Morris traversal first yields leftmost node [OK]

Common Mistakes:

• Assuming next_val is root value initially
• Forgetting thread creation
• Confusing next_val with current node

2. Consider the following code snippet implementing the optimal approach for Two Sum IV in BST. Given the BST with nodes [5,3,6,2,4,null,7] and target k=9, what is the value of variable s during the first iteration of the while loop?

easy

A. 9

B. 5

C. 11

D. 7

Solution

1. Step 1: Perform inorder traversal

   Inorder traversal of BST yields sorted array: [2, 3, 4, 5, 6, 7]

2. Step 2: Calculate s in first iteration

   left=0 (value=2), right=5 (value=7), s = 2 + 7 = 9

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum matches target k=9 on first iteration [OK]

Hint: Inorder array first + last sum equals target [OK]

Common Mistakes:

• Off-by-one error in indexing left or right
• Confusing node values with indices
• Miscomputing sum s

3. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

4. Consider the following buggy code snippet for converting a sorted array to a height-balanced BST. Which line contains the subtle bug that can cause infinite recursion or stack overflow?

medium

A. Line 5: left_child = self.helper(nums, left, mid - 1)

B. Line 3: mid = (left + right) // 2

C. Line 7: root.right = self.helper(nums, mid + 1, right)

D. Line 2: if left >= right: return None

Solution

1. Step 1: Understand base case condition

   The base case should be when left > right, not left >= right, to allow single-element subarrays.

2. Step 2: Consequence of incorrect base case

   Using left >= right causes the recursion to skip processing subarrays of size 1, leading to infinite recursion or missing nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case must allow left == right to process single elements [OK]

Hint: Base case must be left > right, not left >= right [OK]

Common Mistakes:

• Incorrect base case causing infinite recursion
• Misplaced mid calculation

5. What is the time complexity of the optimal iterative algorithm for finding the lowest common ancestor in a BST, where h is the height of the tree and n is the number of nodes?

medium

A. O(log n), assuming the BST is balanced and height h = log n

B. O(n), because in the worst case the algorithm may visit all nodes

C. O(h), since the algorithm traverses from root down to the split point along one path

D. O(1), because the algorithm uses constant space and simple comparisons

Solution

1. Step 1: Identify traversal path length

   The algorithm moves from root down one path until the split point, visiting at most h nodes.

2. Step 2: Understand h vs n

   Height h can be up to n in worst case (skewed tree), but the question asks for optimal algorithm time complexity, which assumes balanced BST where h = log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal limited to one root-to-node path in balanced BST [OK]

Hint: Time depends on tree height, not total nodes [OK]

Common Mistakes:

• Confusing worst-case O(n) with average-case O(log n)
• Assuming constant time due to simple comparisons
• Ignoring that recursion stack space is not used here