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. You are given a sorted array of unique integers and need to construct a binary search tree with minimal height. Which approach guarantees the resulting tree is height-balanced and constructed in O(n) time?

easy

A. Use a divide-and-conquer recursion that picks the middle element as root and recursively builds left and right subtrees.

B. Insert elements one by one into an empty BST using standard BST insertion.

C. Use a greedy approach that always inserts the smallest remaining element as the left child.

D. Build a balanced BST by repeatedly merging two smaller balanced BSTs.

Solution

1. Step 1: Understand the problem constraints

   The input is a sorted array, and the goal is to build a height-balanced BST efficiently.

2. Step 2: Evaluate approaches

   Inserting elements one by one leads to skewed trees and O(n^2) time. Greedy insertion of smallest elements does not guarantee balance. Merging BSTs is not straightforward and inefficient. The divide-and-conquer approach picks the middle element as root, ensuring balanced subtrees and O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Middle element chosen recursively -> balanced BST in O(n) time [OK]

Hint: Middle element recursion ensures balanced BST [OK]

Common Mistakes:

• Thinking inserting one by one is efficient
• Assuming greedy insertion balances tree

2. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to helper with input nums = [1, 3, 5]?

easy

A. 3

B. 1

C. 5

D. None

Solution

1. Step 1: Calculate mid index for initial call

   For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.

2. Step 2: Identify root value

   nums[mid] = nums[1] = 3, so root node value is 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid index calculation picks 3 as root [OK]

Hint: Mid index picks middle element as root [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one mid calculation

3. You are given a binary tree where exactly two nodes have been swapped by mistake, violating the binary search tree property. Which approach guarantees an optimal solution to recover the tree without changing its structure or using extra space beyond a constant amount?

easy

A. Use a bottom-up dynamic programming approach to reconstruct the BST by comparing subtrees and swapping nodes.

B. Perform an inorder traversal, store values in a list, sort the list, then overwrite the tree nodes with sorted values.

C. Apply a greedy approach by swapping any two nodes that violate the BST property during a single inorder traversal pass.

D. Use Morris inorder traversal to detect the two swapped nodes during traversal and swap their values, achieving O(1) space complexity.

Solution

1. Step 1: Understand the problem constraints

   The problem requires recovering a BST where two nodes are swapped, without extra space and without changing the tree structure.

2. Step 2: Identify the approach that meets constraints

   Morris inorder traversal allows inorder traversal without recursion or stack, detecting swapped nodes on the fly and swapping their values, achieving O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Morris traversal is the only approach with O(1) space and no structural changes [OK]

Hint: Morris traversal enables O(1) space recovery [OK]

Common Mistakes:

• Assuming sorting values is optimal despite extra space
• Believing greedy single pass fixes all cases
• Confusing DP with tree recovery

4. You are given a binary search tree and a target integer k. You need to determine if there exist two distinct nodes in the BST whose values sum up to k. Which of the following approaches guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform an inorder traversal to get a sorted array, then use two pointers to find if a pair sums to k.

B. Use dynamic programming to store sums of all subtree pairs and check for k.

C. Perform a brute force nested traversal of all node pairs directly on the BST without extra storage.

D. Use a greedy approach by always choosing the smallest and largest node values and adjusting pointers.

Solution

1. Step 1: Understand BST property and inorder traversal

   Inorder traversal of a BST produces a sorted array of node values.

2. Step 2: Apply two-pointer technique on sorted array

   Using two pointers at start and end, we can efficiently find if two values sum to k in O(n) time and O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder + two pointers is optimal and uses BST ordering [OK]

Hint: Inorder traversal yields sorted array for two-pointer sum [OK]

Common Mistakes:

• Trying nested loops directly on BST nodes without flattening
• Assuming greedy approach works without sorting
• Using DP which is unnecessary here

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