Is this price-ordered tree a valid BST?

Question

A binary search tree requires that every node in a left subtree is smaller, and every node in a right subtree is larger, than the parent, a global rule, not merely a local parent/child check. Verify whether a given tree is a valid BST. Return whether the tree satisfies the BST property.

Accepted Answer

Recurse while carrying an open interval (low, high) that the current node's value must fall within. The root may be anything; going left tightens the upper bound to the parent's value, and going right tightens the lower bound. A node violating its interval fails immediately. Local checks alone miss violations like a small value buried deep in a right subtree. Tracing the second tree: node 4 sits in the right subtree of 5, so its allowed interval is (5, 8); since 4 < 5, validation returns False. Time O(n), space O(h) recursion depth. Edge cases: an empty tree is valid; duplicate values fail th…

Is this price-ordered tree a valid BST?

Your answer

More Coding questions