Verify Strict BST Ordering of a Binary Tree Given in Level Order
Company: Pinduoduo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Overview: Decide whether a binary tree given in level-order form is a strict binary search tree, where every value in a node's entire left subtree is smaller and every value in its entire right subtree is larger. Tests subtree-wide ordering, duplicate values, extreme 32-bit values and deep, unbalanced trees.
Constraints
- 1 <= number of nodes <= 10^4
- -2^31 <= node value <= 2^31 - 1; the two extreme values themselves may occur (every node value fits in a signed 32-bit integer).
- The tree is not necessarily balanced; its height can be as large as the number of nodes.
- tree[0] is the root and is never None; a missing node has no child slots; trailing None entries may be omitted.
- tree holds at most 2 * 10^4 + 1 entries (a consequence of the encoding).
Examples
Input: ([-2147483648],)
Expected Output: True
Explanation: Minimum valid: a single node holding -2^31 is a valid tree.
Input: ([2147483647],)
Expected Output: True
Explanation: Minimum valid: a single node holding 2^31 - 1 is a valid tree.
Hints
- Comparing each node only with its direct children is not enough: in Example 2, node 9 is greater than its parent 3 but lies in the root's left subtree, so it must also be less than 8.
- A missing node contributes no child slots, so a node's children are not always at positions 2i + 1 and 2i + 2 of the list.
- The tree may be a single chain 10^4 nodes tall, and node values may equal -2^31 or 2^31 - 1 exactly.