Sign in
Skip to solution
mediumDSA

How do you validate that a binary tree is a BST?

843 views
01

Understand the problem

Explain BST validation.

treesbst
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Recurse with a (min, max) range for each node, narrowing it as you descend left (tighten max) and right (tighten min); a node violating its range fails. Equivalently, an inorder traversal of a valid BST is strictly increasing. O(n).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Range-bounds validation
Run Playground
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

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


# --- demo ---
valid = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8, None, TreeNode(9)))
invalid = TreeNode(8, TreeNode(4), TreeNode(12, TreeNode(7), None))   # 7 < 8 deep on the right
print(is_valid_bst(valid))     # True
print(is_valid_bst(invalid))   # False
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 44 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track