trees · Problem 1 of 3

Validate Binary Search Tree

medium

Amazon

Microsoft

Bloomberg

Meta

Given the root of a binary tree (represented as { value, left, right } nodes with null for missing children), determine if it is a valid Binary Search Tree (BST).

A valid BST is defined as:

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.

isValidBST({ value: 2, left: { value: 1, left: null, right: null }, right: { value: 3, left: null, right: null } }) -> true

Your solution

input

Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.

Running is free — Submit is what records it. Or press ⌘↩

Tests

4 cases, 1 hidden

call	type	expected	result
isValidBST({"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}})	valid small BST	true	—
isValidBST({"value":5,"left":{"value":1,"left":null,"right":null},"right":{"value":4,"left":{"value":3,"left":null,"right":null},"right":{"value":6,"left":null,"right":null}}})	invalid right subtree child violation	false	—
isValidBST(null)	empty tree is valid	true	—
withheld	hidden	withheld	—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time: O(n)
target space: O(h) where h is tree height

Visits each node once while carrying upper and lower bounding constraints down the recursion stack.

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left