Determine whether a binary tree obeys the strict binary-search-tree rule. Every value in a node's left subtree must be smaller than that node, and every value in its right subtree must be larger. Duplicate values are invalid. An empty tree is valid. The course supplies nodes with data, left, and right fields.
Carry ancestor bounds into each subtree
Checking a node against only its immediate children is insufficient. Consider root 10, left child 5, and 5's right child 12. Twelve is greater than its parent 5, but it still belongs to the left subtree of 10 and violates that ancestor's constraint.
Pass an allowed lower and upper bound into each recursive call. A node must fall strictly between them. Its left child inherits the lower bound and receives the current value as a new upper bound. Its right child receives the current value as a new lower bound and inherits the upper bound. A null child satisfies the rule because there are no values to violate it.
Trace a violation below a valid edge
At root 10, the initial interval permits every input value. Descending left to 5 narrows the interval to values below 10. Descending right from 5 narrows it again to values greater than 5 but still below 10. Value 12 fails that combined interval immediately.
For a valid tree with root 10, left child 5, and 5's right child 7, the same final interval accepts 7. The bounds summarize every ancestor decision on the path, so each node can be validated without rereading that path or scanning its entire subtree.
Prove the recursive condition
A subtree is valid when its root satisfies the inherited bounds and both child subtrees satisfy their newly narrowed bounds. The left child's upper bound forces every descendant in that subtree below the current root. The right child's lower bound forces every descendant above it. Inherited bounds continue to enforce all earlier ancestors.
The null base case and those two conditions establish the result by induction on subtree size. Returning true after checking only the current root would miss deeper violations. Returning the left result without the right result would ignore half the tree. Both recursive results are necessary, although a short-circuit implementation may stop after the first failure.
Choose sentinels that admit endpoint values
An initial exclusive bound equal to the minimum input integer would incorrectly reject that exact integer as a root. JavaScript can use infinities; other implementations use a wider bound type or optional bounds. Inspect the code's actual choice before changing the input type. Arithmetic such as value - 1 is unnecessary and can overflow at endpoints.
An alternative validates that an in-order traversal produces strictly increasing values. That method also needs a safe representation for the absence of a previous value. It should reject equality rather than silently allowing duplicates. Both methods express the same strict ordering contract, but their state and implementation differ.
Costs and tests that reach ancestors
The bound-based traversal visits at most n nodes, giving O(n) time. Recursive storage is O(h), where h is tree height. A balanced tree has logarithmic height; a chain has linear height. Large skewed inputs may need an explicit stack to avoid the language's recursion limit.
Test empty and singleton trees, duplicate values on either side, minimum and maximum input integers, and a deep node that violates a distant ancestor while satisfying its parent. Include both left and right chains. For an independent oracle, collect an in-order sequence and require every adjacent pair to increase strictly. A follow-up can allow duplicates on one designated side, but then every equality rule and inherited bound needs to match that policy.
Python implementation
The recursive bounds use numeric infinities. The null base case accepts an empty subtree without reading any node fields.
Python entries use the function or class API shown in the lesson starter. Lists and dictionaries are mutable, and assignment shares those objects. Integer arithmetic has arbitrary precision, although the course input and output schema still has bounded integer types. Recursive solutions use Python call frames; an iterative rewrite is appropriate when input depth can exceed the interpreter's recursion limit.
def recursive_validate(root, lower_bound, upper_bound):
# Base case 1 (reached leaf, valid)
if root == None:
return True
# Base case 2 (invalid)
if (root.data <= lower_bound) or (root.data >= upper_bound):
return False
# When we traverse left, the current node's value must be the newest upper bound
# This ensures it's always strictly decreaseing from the current node
is_valid_left = recursive_validate(root.left, lower_bound, root.data)
# When we traverse right, the current node's value must be the newest lower bound
# This ensures it's always strictly increasing from the current node
is_valid_right = recursive_validate(root.right, root.data, upper_bound)
# Both must be true for this to return true
return (is_valid_left and is_valid_right)
def is_bst(root):
is_valid = recursive_validate(root, float("-inf"), float("inf"))
return is_valid
Practice this implementation
Open BST Validate to run the implementation against the course tests, then change one boundary condition and explain the first failing case. The editor supplies the starter signature and any node types or helper APIs used above. Copy the implementation into that environment; the snippet is the solution body, without the input parser or test driver. Your saved progress belongs to the original lesson.
For more Python conventions and practice problems, use the Python interview guide.