Validate Binary Search Tree

🎯

Validate Binary Search Tree

mediumTREEAmazonFacebookGoogle

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.

💡 This problem tests understanding of the binary search tree (BST) property, which can be tricky because it requires checking all nodes against a range, not just their immediate children. Beginners often confuse local node comparisons with global BST validity.

📋

Problem Statement

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.

💡

Example

Input"root = [2,1,3]"

Outputtrue

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

Input"root = [5,1,4,null,null,3,6]"

Outputfalse

The tree: 5 / \ 1 4 / \ 3 6 Node 4's left child 3 is less than 5 but appears in the right subtree of 5, violating BST rules.

• Single node tree → true
• Tree with duplicate values → false (BST requires strictly less/greater)
• Left skewed tree (all nodes have only left child) → true if values strictly decreasing
• Right skewed tree (all nodes have only right child) → true if values strictly increasing

⚠️

Common Mistakes

Only comparing node with immediate children

Fails to detect invalid BSTs where descendants violate BST property

✅ Use min/max range or inorder traversal to check global BST property

Allowing duplicates as valid BST nodes

Incorrectly returns true for trees with duplicate values violating strict inequality

✅ Use strict less than and greater than comparisons, not less than or equal

Not resetting global variables between test cases

Incorrect results when running multiple tests in same program

✅ Reset variables like 'prev' before each test

Using integer min/max instead of long or float for range bounds

Fails on edge cases with node values at integer limits

✅ Use long (Java/C++), float('-inf') or -Infinity (Python/JS) to represent bounds

🧠

Brute Force (Check Subtree Min/Max for Each Node)

💡 This approach is intuitive and helps understand the BST property by explicitly checking all nodes in left and right subtrees for each node, but it is inefficient.

Intuition

For each node, verify that all nodes in its left subtree are less than it and all nodes in its right subtree are greater than it by traversing those subtrees.

Algorithm

1. For each node, find the maximum value in its left subtree.
2. Find the minimum value in its right subtree.
3. Check if the node's value is greater than the max in left subtree and less than the min in right subtree.
4. Recursively apply this check to all nodes.

💡 This algorithm is hard to see as efficient because it repeats subtree traversals multiple times, leading to redundant work.

</>

Code

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

def find_max(node):
    if not node:
        return float('-inf')
    return max(node.val, find_max(node.left), find_max(node.right))

def find_min(node):
    if not node:
        return float('inf')
    return min(node.val, find_min(node.left), find_min(node.right))

def is_valid_bst(root):
    if not root:
        return True
    left_max = find_max(root.left)
    right_min = find_min(root.right)
    if root.val <= left_max or root.val >= right_min:
        return False
    return is_valid_bst(root.left) and is_valid_bst(root.right)

# Driver code to test
if __name__ == '__main__':
    root = TreeNode(2, TreeNode(1), TreeNode(3))
    print(is_valid_bst(root))  # Expected: True
    root2 = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
    print(is_valid_bst(root2))  # Expected: False

Line Notes

class TreeNode:Define TreeNode class to represent nodes in the binary tree

def find_max(node):Helper to find max value in subtree, needed to check BST property

if not node:Base case returns infinity so empty subtree doesn't affect min

return max(node.val, find_max(node.left), find_max(node.right))Recursively find max in entire subtree

def find_min(node):Helper to find min value in subtree, needed to check BST property

return min(node.val, find_min(node.left), find_min(node.right))Recursively find min in entire subtree

left_max = find_max(root.left)Find max in left subtree to compare with current node

right_min = find_min(root.right)Find min in right subtree to compare with current node

if root.val <= left_max or root.val >= right_min:Check BST property violation at current node

return is_valid_bst(root.left) and is_valid_bst(root.right)Recursively validate left and right subtrees

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int findMax(TreeNode node) {
        if (node == null) return Integer.MIN_VALUE;
        return Math.max(node.val, Math.max(findMax(node.left), findMax(node.right)));
    }

    public int findMin(TreeNode node) {
        if (node == null) return Integer.MAX_VALUE;
        return Math.min(node.val, Math.min(findMin(node.left), findMin(node.right)));
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        int leftMax = findMax(root.left);
        int rightMin = findMin(root.right);
        if (root.val <= leftMax || root.val >= rightMin) return false;
        return isValidBST(root.left) && isValidBST(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(sol.isValidBST(root)); // true
        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(4);
        root2.right.left = new TreeNode(3);
        root2.right.right = new TreeNode(6);
        System.out.println(sol.isValidBST(root2)); // false
    }
}

Line Notes

class TreeNode {Define TreeNode class to represent nodes in the binary tree

public int findMax(TreeNode node) {Helper to find max value in subtree for BST check

if (node == null) return Integer.MIN_VALUE;Base case returns minimal int so empty subtree doesn't affect max

return Math.max(node.val, Math.max(findMax(node.left), findMax(node.right)));Recursively find max in entire subtree

public int findMin(TreeNode node) {Helper to find min value in subtree for BST check

if (node == null) return Integer.MAX_VALUE;Base case returns max int so empty subtree doesn't affect min

return Math.min(node.val, Math.min(findMin(node.left), findMin(node.right)));Recursively find min in entire subtree

int leftMax = findMax(root.left);Find max in left subtree to compare with current node

int rightMin = findMin(root.right);Find min in right subtree to compare with current node

if (root.val <= leftMax || root.val >= rightMin) return false;Check BST property violation at current node

return isValidBST(root.left) && isValidBST(root.right);Recursively validate left and right subtrees

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int findMax(TreeNode* node) {
    if (!node) return INT_MIN;
    return max(node->val, max(findMax(node->left), findMax(node->right)));
}

int findMin(TreeNode* node) {
    if (!node) return INT_MAX;
    return min(node->val, min(findMin(node->left), findMin(node->right)));
}

bool isValidBST(TreeNode* root) {
    if (!root) return true;
    int leftMax = findMax(root->left);
    int rightMin = findMin(root->right);
    if (root->val <= leftMax || root->val >= rightMin) return false;
    return isValidBST(root->left) && isValidBST(root->right);
}

int main() {
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    cout << boolalpha << isValidBST(root) << endl; // true
    TreeNode* root2 = new TreeNode(5);
    root2->left = new TreeNode(1);
    root2->right = new TreeNode(4);
    root2->right->left = new TreeNode(3);
    root2->right->right = new TreeNode(6);
    cout << boolalpha << isValidBST(root2) << endl; // false
    return 0;
}

Line Notes

struct TreeNode {Define TreeNode struct to represent nodes in the binary tree

int findMax(TreeNode* node) {Helper to find max value in subtree for BST validation

if (!node) return INT_MIN;Base case returns minimal int so empty subtree doesn't affect max

return max(node->val, max(findMax(node->left), findMax(node->right)));Recursively find max in entire subtree

int findMin(TreeNode* node) {Helper to find min value in subtree for BST validation

if (!node) return INT_MAX;Base case returns max int so empty subtree doesn't affect min

return min(node->val, min(findMin(node->left), findMin(node->right)));Recursively find min in entire subtree

int leftMax = findMax(root->left);Find max in left subtree to compare with current node

int rightMin = findMin(root->right);Find min in right subtree to compare with current node

if (root->val <= leftMax || root->val >= rightMin) return false;Check BST property violation at current node

return isValidBST(root->left) && isValidBST(root->right);Recursively validate left and right subtrees

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findMax(node) {
    if (!node) return -Infinity;
    return Math.max(node.val, findMax(node.left), findMax(node.right));
}

function findMin(node) {
    if (!node) return Infinity;
    return Math.min(node.val, findMin(node.left), findMin(node.right));
}

function isValidBST(root) {
    if (!root) return true;
    const leftMax = findMax(root.left);
    const rightMin = findMin(root.right);
    if (root.val <= leftMax || root.val >= rightMin) return false;
    return isValidBST(root.left) && isValidBST(root.right);
}

// Test cases
const root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
console.log(isValidBST(root)); // true
const root2 = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
console.log(isValidBST(root2)); // false

Line Notes

class TreeNode {Define TreeNode class to represent nodes in the binary tree

function findMax(node) {Helper to find max value in subtree for BST check

if (!node) return -Infinity;Base case returns minimal number so empty subtree doesn't affect max

return Math.max(node.val, findMax(node.left), findMax(node.right));Recursively find max in entire subtree

function findMin(node) {Helper to find min value in subtree for BST check

if (!node) return Infinity;Base case returns max number so empty subtree doesn't affect min

return Math.min(node.val, findMin(node.left), findMin(node.right));Recursively find min in entire subtree

const leftMax = findMax(root.left);Find max in left subtree to compare with current node

const rightMin = findMin(root.right);Find min in right subtree to compare with current node

if (root.val <= leftMax || root.val >= rightMin) return false;Check BST property violation at current node

return isValidBST(root.left) && isValidBST(root.right);Recursively validate left and right subtrees

⏱

Complexity

TimeO(n^2)

SpaceO(n) due to recursion stack and subtree traversals

For each node, we traverse its entire left and right subtrees to find min and max, leading to repeated work and quadratic time.

💡 For n=20 nodes, this approach might do up to 400 operations, which grows quickly and is inefficient for large trees.

Interview Verdict: TLE / Inefficient

This approach is too slow for large inputs but is useful to understand the BST property deeply before optimizing.

🧠

Better (Top-Down Min/Max Range Validation)

💡 This approach uses the BST property as a range constraint passed down the tree, avoiding repeated subtree traversals and improving efficiency.

Intuition

Each node must lie within a valid range defined by its ancestors. We recursively check if node values respect these min and max bounds.

Algorithm

1. Start with the root node and an initial range (-infinity, +infinity).
2. Check if the current node's value lies within the allowed range.
3. Recursively validate the left subtree with updated max bound as current node's value.
4. Recursively validate the right subtree with updated min bound as current node's value.

💡 Passing down constraints is a key insight that avoids redundant subtree scans and ensures global BST validity.

</>

Code

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

def is_valid_bst(root):
    def helper(node, low, high):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False
        return helper(node.left, low, node.val) and helper(node.right, node.val, high)
    return helper(root, float('-inf'), float('inf'))

# Driver code
if __name__ == '__main__':
    root = TreeNode(2, TreeNode(1), TreeNode(3))
    print(is_valid_bst(root))  # True
    root2 = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
    print(is_valid_bst(root2))  # False

Line Notes

class TreeNode:Define TreeNode class to represent nodes in the binary tree

def is_valid_bst(root):Main function to validate BST using helper

def helper(node, low, high):Helper function carries current valid range for node values

if not node:Base case: empty subtree is valid

if node.val <= low or node.val >= high:Check if current node violates BST range constraints

return helper(node.left, low, node.val) and helper(node.right, node.val, high)Recursively validate left and right subtrees with updated ranges

return helper(root, float('-inf'), float('inf'))Start recursion with full range

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean helper(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return helper(node.left, low, node.val) && helper(node.right, node.val, high);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(sol.isValidBST(root)); // true
        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(4);
        root2.right.left = new TreeNode(3);
        root2.right.right = new TreeNode(6);
        System.out.println(sol.isValidBST(root2)); // false
    }
}

Line Notes

class TreeNode {Define TreeNode class to represent nodes in the binary tree

public boolean isValidBST(TreeNode root) {Entry point calls helper with full integer range

private boolean helper(TreeNode node, long low, long high) {Helper function with range constraints passed as long to avoid overflow

if (node == null) return true;Empty subtree is valid BST

if (node.val <= low || node.val >= high) return false;Check if node violates allowed range

return helper(node.left, low, node.val) && helper(node.right, node.val, high);Recurse with updated bounds for left and right subtrees

#include <iostream>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool helper(TreeNode* node, long low, long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return helper(node->left, low, node->val) && helper(node->right, node->val, high);
}

bool isValidBST(TreeNode* root) {
    return helper(root, LONG_MIN, LONG_MAX);
}

int main() {
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    cout << boolalpha << isValidBST(root) << endl; // true
    TreeNode* root2 = new TreeNode(5);
    root2->left = new TreeNode(1);
    root2->right = new TreeNode(4);
    root2->right->left = new TreeNode(3);
    root2->right->right = new TreeNode(6);
    cout << boolalpha << isValidBST(root2) << endl; // false
    return 0;
}

Line Notes

struct TreeNode {Define TreeNode struct to represent nodes in the binary tree

bool helper(TreeNode* node, long low, long high) {Helper function with range constraints passed as long to avoid overflow

if (!node) return true;Empty subtree is valid BST

if (node->val <= low || node->val >= high) return false;Check if node violates BST property with current bounds

return helper(node->left, low, node->val) && helper(node->right, node->val, high);Recurse with updated bounds for left and right subtrees

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isValidBST(root) {
    function helper(node, low, high) {
        if (!node) return true;
        if (node.val <= low || node.val >= high) return false;
        return helper(node.left, low, node.val) && helper(node.right, node.val, high);
    }
    return helper(root, -Infinity, Infinity);
}

// Test cases
const root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
console.log(isValidBST(root)); // true
const root2 = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
console.log(isValidBST(root2)); // false

Line Notes

class TreeNode {Define TreeNode class to represent nodes in the binary tree

function isValidBST(root) {Main function to validate BST using helper

function helper(node, low, high) {Helper function carries current valid range for node values

if (!node) return true;Empty subtree is valid BST

if (node.val <= low || node.val >= high) return false;Check if node violates BST property with current bounds

return helper(node.left, low, node.val) && helper(node.right, node.val, high);Recurse with updated bounds for left and right subtrees

⏱

Complexity

TimeO(n)

SpaceO(h) where h is tree height due to recursion stack

Each node is visited once, and range checks are O(1), so linear time. Space depends on recursion depth.

💡 For n=20 nodes in a balanced tree, recursion depth is about 5, so space is small and time is efficient.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews.

🧠

Optimal (Inorder Traversal Check)

💡 This approach leverages the property that inorder traversal of a BST yields a strictly increasing sequence, allowing a simple linear scan.

Intuition

Perform an inorder traversal and check if the values are strictly increasing. If not, the tree is not a BST.

Algorithm

1. Initialize a variable to track the previous node's value during traversal.
2. Perform an inorder traversal (left, node, right).
3. At each node, check if current node's value is greater than the previous value.
4. If any node violates this, return false; otherwise, return true after traversal.

💡 This algorithm is elegant because it reduces the problem to a simple sorted sequence check.

</>

Code

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

def is_valid_bst(root):
    prev = [float('-inf')]
    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)
    return inorder(root)

# Driver code
if __name__ == '__main__':
    root = TreeNode(2, TreeNode(1), TreeNode(3))
    print(is_valid_bst(root))  # True
    root2 = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
    print(is_valid_bst(root2))  # False

Line Notes

class TreeNode:Define TreeNode class to represent nodes in the binary tree

prev = [float('-inf')]Use list to hold previous value so it is mutable in nested function

def inorder(node):Inorder traversal helper function

if not node:Base case: empty subtree is valid

if not inorder(node.left):Recursively traverse left subtree and check validity

if node.val <= prev[0]:Check if current node violates ascending order property

prev[0] = node.valUpdate previous value after visiting current node

return inorder(node.right)Recursively traverse right subtree and check validity

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (root.val <= prev) return false;
        prev = root.val;
        return isValidBST(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(sol.isValidBST(root)); // true
        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(4);
        root2.right.left = new TreeNode(3);
        root2.right.right = new TreeNode(6);
        System.out.println(sol.isValidBST(root2)); // false
    }
}

Line Notes

class TreeNode {Define TreeNode class to represent nodes in the binary tree

private long prev = Long.MIN_VALUE;Track previous node value globally for inorder traversal

public boolean isValidBST(TreeNode root) {Main function to validate BST using inorder traversal

if (root == null) return true;Empty subtree is valid BST

if (!isValidBST(root.left)) return false;Traverse left subtree first

if (root.val <= prev) return false;Check if current node violates ascending order

prev = root.val;Update previous value after visiting current node

return isValidBST(root.right);Traverse right subtree

#include <iostream>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

long prevVal = LONG_MIN;

bool isValidBST(TreeNode* root) {
    if (!root) return true;
    if (!isValidBST(root->left)) return false;
    if (root->val <= prevVal) return false;
    prevVal = root->val;
    return isValidBST(root->right);
}

int main() {
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    cout << boolalpha << isValidBST(root) << endl; // true
    prevVal = LONG_MIN; // reset before next test
    TreeNode* root2 = new TreeNode(5);
    root2->left = new TreeNode(1);
    root2->right = new TreeNode(4);
    root2->right->left = new TreeNode(3);
    root2->right->right = new TreeNode(6);
    cout << boolalpha << isValidBST(root2) << endl; // false
    return 0;
}

Line Notes

struct TreeNode {Define TreeNode struct to represent nodes in the binary tree

long prevVal = LONG_MIN;Global variable to track previous node value during inorder traversal

bool isValidBST(TreeNode* root) {Main function to validate BST using inorder traversal

if (!root) return true;Empty subtree is valid BST

if (!isValidBST(root->left)) return false;Traverse left subtree first

if (root->val <= prevVal) return false;Check if current node violates ascending order

prevVal = root->val;Update previous value after visiting current node

return isValidBST(root->right);Traverse right subtree

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isValidBST(root) {
    let prev = -Infinity;
    function inorder(node) {
        if (!node) return true;
        if (!inorder(node.left)) return false;
        if (node.val <= prev) return false;
        prev = node.val;
        return inorder(node.right);
    }
    return inorder(root);
}

// Test cases
const root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
console.log(isValidBST(root)); // true
const root2 = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
console.log(isValidBST(root2)); // false

Line Notes

class TreeNode {Define TreeNode class to represent nodes in the binary tree

let prev = -Infinity;Track previous node value during inorder traversal

function inorder(node) {Inorder traversal helper function

if (!node) return true;Empty subtree is valid BST

if (!inorder(node.left)) return false;Traverse left subtree first

if (node.val <= prev) return false;Check if current node violates ascending order

prev = node.val;Update previous value after visiting current node

return inorder(node.right);Traverse right subtree

⏱

Complexity

TimeO(n)

SpaceO(h) due to recursion stack, h = tree height

Each node is visited once in inorder traversal, and checks are O(1). Space depends on recursion depth.

💡 For a balanced tree with 20 nodes, recursion depth is about 5, so space usage is minimal and time is linear.

Interview Verdict: Accepted

This is the most elegant and commonly preferred approach in interviews due to simplicity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 3 (inorder traversal) is usually the best to code due to its simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down Range Validation	O(n)	O(h)	Yes (deep recursion)	N/A	Good to explain and code if comfortable
3. Inorder Traversal Check	O(n)	O(h)	Yes (deep recursion)	N/A	Best approach to code in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the BST property, then explain brute force to show understanding, followed by optimized approaches. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the BST definition and constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the top-down range validation approach for efficiency.Step 4: Present the inorder traversal approach as the optimal solution.Step 5: Code the chosen approach and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of BST properties, ability to optimize naive solutions, and correctness in handling edge cases like duplicates and skewed trees.

Common Follow-ups

• What if duplicates are allowed on the left or right? → Adjust comparison operators accordingly.
• Can you do this iteratively? → Use iterative inorder traversal with a stack.

💡 These follow-ups test your flexibility in adapting BST definitions and your ability to implement iterative solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves verifying BST property; 2) Input is a binary tree; 3) Need to check ordering constraints; 4) Output is boolean validity.

Signature Phrases

valid binary search treeleft subtree less than noderight subtree greater than node

NOT This Pattern When

Binary tree traversal problems without ordering constraints, or balanced tree construction problems.

Similar Problems

Convert Sorted Array to BST - builds BST from sorted dataKth Smallest Element in BST - uses inorder traversal propertyLowest Common Ancestor of BST - uses BST ordering for efficient search

Practice

1. Given the following code for inserting a value into a BST, what will be the value of the variable parent.val when inserting 5 into the BST rooted at 4 with left child 2 and right child 7?

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

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    parent = None
    while curr:
        parent = curr
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
val = 5
insertIntoBST(root, val)

easy

A. 4

B. 7

C. 2

D. 5

Solution

1. Step 1: Trace insertion path

   Start at root (4). Since 5 > 4, move right to node 7. Update parent to 4.

2. Step 2: Check right child of 7

   5 < 7, so move left. Left child of 7 is None, so insert here. Parent is now 7, but last parent before insertion was 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Parent is last non-null node before insertion -> 4 [OK]

Hint: Parent tracks last node before insertion point [OK]

Common Mistakes:

• Confusing parent with current node
• Off-by-one in loop iteration
• Mistaking inserted value as parent

2. 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

3. Suppose you want to extend the BST Iterator to support repeated calls to next() that return the same element multiple times (i.e., allow reuse of elements). Which modification to the Morris traversal based iterator is correct?

hard

A. Remove thread restoration to keep the tree threaded and allow repeated visits to the same node.

B. Store all elements in a list during initialization to allow repeated next() calls without traversal.

C. Modify _advance() to not move current pointer after returning next_val, so next() returns same value again.

D. Use a stack-based iterator and push nodes multiple times to simulate repeated next() calls.

Solution

1. Step 1: Understand reuse requirement

   Allowing repeated next() calls to return the same element requires storing elements since Morris traversal advances and loses previous state.

2. Step 2: Evaluate modifications

   Removing thread restoration (A) corrupts tree, modifying _advance() to not move current (C) breaks traversal logic, and pushing nodes multiple times on stack (B) is inefficient and incorrect. Storing all elements upfront (D) enables repeated next() calls reliably.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pre-storing elements supports repeated next() calls without traversal [OK]

Hint: Reuse requires storing elements, not traversal tricks [OK]

Common Mistakes:

• Assuming traversal can be paused and repeated
• Ignoring tree corruption from missing restoration
• Trying to simulate reuse with threads

4. Suppose the BST can contain duplicate values, and you want to find the lowest common ancestor of two nodes p and q that may have the same value. Which modification to the optimal iterative algorithm correctly handles duplicates while maintaining efficiency?

hard

A. Define a consistent rule that duplicates go to the right subtree and use original algorithm without changes.

B. Modify comparisons to use '<=' and '>=' to ensure traversal includes duplicates on both sides.

C. Augment each node with a count of duplicates and traverse left or right based on counts to find LCA.

D. Store paths from root to p and q and compare them to find LCA, since BST property is ambiguous with duplicates.

Solution

1. Step 1: Understand duplicate handling in BST

   BSTs with duplicates require a consistent insertion rule, commonly duplicates go to right subtree.

2. Step 2: Modify comparisons to include duplicates

   Using '<=' and '>=' in comparisons ensures traversal includes duplicates correctly on both sides.

3. Step 3: Avoid ambiguous or inefficient methods

   Path comparison or augmenting nodes adds overhead and complexity.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Inclusive comparisons handle duplicates while preserving efficiency [OK]

Hint: Modify comparison operators to handle duplicates correctly [OK]

Common Mistakes:

• Using strict comparisons that miss duplicates
• Reverting to path comparison losing efficiency
• Adding unnecessary data structures

5. Suppose the BST can contain duplicate values and you want to find if there exist two nodes (not necessarily distinct) whose values sum to k. Which modification to the optimal inorder + two-pointer approach correctly handles this scenario?

hard

A. Perform inorder traversal and remove duplicates before applying two-pointer technique.

B. Use the same two-pointer approach but allow left and right pointers to point to the same index.

C. Use a hash set to store values and check complements, ignoring duplicates.

D. During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST.

Solution

1. Step 1: Understand duplicates and two-pointer constraints

   Two-pointer approach requires two distinct indices; if pointers meet, need to verify if duplicate values exist.

2. Step 2: Modify check when left == right

   Check if the value at that index occurs at least twice in the BST to allow sum with itself.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST. correctly handles duplicates without breaking two-pointer logic [OK]

Hint: Check duplicates count when pointers meet [OK]

Common Mistakes:

• Allowing pointers to be equal without duplicate check
• Removing duplicates loses valid pairs
• Ignoring duplicates in hash set approach