Show problems as
Classic problem #98MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Validate Binary Search Tree

Real-world version: Archive Index Order
Tracked in this browser only
Read Validate Binary Search Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstTraversal & Search · Binary Trees & BST, animated step by step

A records office hangs its drawers in a lookup tree. Every drawer is stamped with one signed shelf code, and a drawer may carry up to two drawers beneath it: one on its low hook and one on its high hook.

The office claims to file by a strict rule. Take any drawer in the tree. Every code in the branch hanging off that drawer's low hook must be smaller than the drawer's own code, and every code in the branch hanging off its high hook must be larger. A branch here means the drawer sitting on that hook together with every drawer hanging below it, at any depth. Because the comparisons are strict, no code can appear twice in a properly filed tree.

Because the harness passes plain JSON, the tree reaches you as the array drawers, read level by level from the top drawer downwards. The first entry is the top drawer's code. After that the entries arrive in pairs, giving the low-hook drawer and then the high-hook drawer of each drawer already listed, in that same level order. A hook carrying nothing is written null, and a null contributes no pair of its own. The array stops once nothing is left to describe, so null entries that would trail at the very end may be left off.

Return true when every drawer in the tree satisfies the filing rule, and false when at least one drawer does not.

Examples

Example 1

Input
drawers = [40, 25, 60, null, null, 55, 80]
Output
true

Below the top drawer the low branch holds only 25 and the high branch holds 55, 60 and 80, all above 40. Drawer 60 also splits its own hooks correctly at 55 and 80.

Example 2

Input
drawers = [40, 25, 60, null, null, 30, 80]
Output
false

Drawer 30 hangs on the low hook of 60, so it sits inside the high branch of 40, and every code in that branch has to exceed 40.

Example 3

Input
drawers = [12, 7, 12]
Output
false

The high hook repeats the top drawer's code. Codes on a high hook have to be strictly larger, so a tie breaks the rule.

Constraints

  • The number of drawers in the tree is in the range [1, 10^4].
  • -2^31 <= drawers[i] <= 2^31 - 1 for every entry that is not `null`.
  • A `null` entry marks a hook carrying nothing and contributes no pair of its own.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def archive_index_order(drawers: list) -> bool:
Java
public boolean archiveIndexOrder(Integer[] drawers)

More on the same topics