Medium · Depth-First Search
Understand → Visualise → Practice.
In a binary search tree every value in the left subtree is smaller than the node, and every value in the right subtree is larger.
Each node must lie inside a range inherited from its ancestors. Going left lowers the upper bound; going right raises the lower bound.
Anything goes at the top.
low < val < high, otherwise fail.
Left: (low, val). Right: (val, high).
O(n) time, O(h) space.
Comparing a node only with its children is not enough: 9 in the example is a right child of 6 but sits under the root's left side.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.