{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Validate Binary Search Tree – Solution & Complexity

Interview solutions
/
Validate Binary Search Tree

Solution Walkthrough

1. Recognize the Pattern

The key pattern is: DFS carries the full valid value range. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(n). Space: O(h).

Java/Go/Rust below are reference solutions for learning the pattern in those languages; only Python and JavaScript can be run and submitted for this problem, since the remote judge doesn't support the TreeNode structure yet.

def is_valid_bst(root: TreeNode) -> bool:
    def valid(node, low, high):
        if node is None:
            return True
        return low < node.val < high and valid(node.left, low, node.val) and valid(node.right, node.val, high)
    return valid(root, float("-inf"), float("inf"))

FAQ

See also

Practice Validate Binary Search Tree online (run code in the browser)Lowest Common Ancestor of a BST solution (medium)Invert Binary Tree solution (easy)Maximum Depth of Binary Tree solution (easy)Same Tree solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?