Quick 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.

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

Given a binary tree of integers, decide whether it is a binary search tree with strict ordering. The ordering condition applies to each node's entire left and right subtrees, not only to its direct children. ### Function Signature ```python def is_strict_bst(tree: list[int | None]) -> bool: ``` ### Rules - `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with `None` for a missing child; a missing node has no child slots. Trailing `None` entries may be omitted. `tree[0]` is the root and is never `None`. - A node with value `v` satisfies the ordering condition when every value in its entire left subtree is strictly less than `v` and every value in its entire right subtree is strictly greater than `v`. An empty subtree imposes no condition. - Because both comparisons are strict, a tree in which two nodes hold the same value is never valid. - Return `True` if every node satisfies the condition and `False` otherwise. A single-node tree is valid. ### Constraints - `1 <= number of nodes <= 10^4` - `-2^31 <= node value <= 2^31 - 1`; the two extreme values themselves may occur. - The tree is not necessarily balanced; its height can be as large as the number of nodes. ### Examples **Example 1** ```text Input: tree = [8, 3, 10, 1, 6, None, 14] Output: True ``` ```text 8 / \ 3 10 / \ \ 1 6 14 ``` The root's left subtree holds `{3, 1, 6}`, all less than 8, and its right subtree holds `{10, 14}`, all greater than 8. Node 3 has 1 on its left and 6 on its right, and node 10 has 14 on its right, so every node satisfies the condition. **Example 2** ```text Input: tree = [8, 3, 10, 1, 9] Output: False ``` ```text 8 / \ 3 10 / \ 1 9 ``` Node 9 is greater than its parent 3, which is correct for node 3, but 9 lies in the root's left subtree and is not less than 8. **Example 3** ```text Input: tree = [4, 2, 6, 1, 4] Output: False ``` ```text 4 / \ 2 6 / \ 1 4 ``` The second 4 lies in the root's left subtree and is equal to the root's value, so the strict condition `value < 4` fails.

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.

Given a binary tree of integers, decide whether it is a binary search tree with strict ordering. The ordering condition applies to each node's entire left and right subtrees, not only to its direct children. ### Input format - `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, left then right, with `None` for a missing child. A missing node has no child slots. Trailing `None` entries may be omitted. - `tree[0]` is the root and is never `None`. - Language types: Python `list[int | None]`; JavaScript an array of numbers and `null`; Java `java.util.List<Integer>` with `null` entries; C++ `std::vector<std::optional<int>>` with `std::nullopt` entries. ### Rules - A node with value `v` satisfies the ordering condition when every value in its entire left subtree is strictly less than `v` and every value in its entire right subtree is strictly greater than `v`. An empty subtree imposes no condition. - Because both comparisons are strict, a tree in which two nodes hold the same value is never valid. - Return `True` if every node satisfies the condition and `False` otherwise (`true` / `false` in JavaScript, Java and C++). A single-node tree is valid. ### Example 1 ```text Input: tree = [8, 3, 10, 1, 6, None, 14] Output: True ``` The root 8 has left child 3 and right child 10; node 3 has children 1 and 6; node 10 has only a right child, 14. The root's left subtree holds {3, 1, 6}, all less than 8, and its right subtree holds {10, 14}, all greater than 8. Node 3 has 1 on its left and 6 on its right, and node 10 has 14 on its right, so every node satisfies the condition. ### Example 2 ```text Input: tree = [8, 3, 10, 1, 9] Output: False ``` The root 8 has children 3 and 10, and node 3 has children 1 and 9. Node 9 is greater than its parent 3, which is correct for node 3, but 9 lies in the root's left subtree and is not less than 8. ### 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. - Because of the encoding, `tree` holds at most `2 * 10^4 + 1` entries.

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

  1. 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.
  2. 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.
  3. The tree may be a single chain 10^4 nodes tall, and node values may equal -2^31 or 2^31 - 1 exactly.

Validate a Strict Binary Search Tree Given in Level Order

mediumPinduoduoSoftware Engineer

Given a binary tree of integers, decide whether it is a binary search tree with strict ordering. The ordering condition applies to each node's entire left and right subtrees, not only to its direct children.

Input format

  • tree is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, left then right, with None for a missing child. A missing node has no child slots. Trailing None entries may be omitted.
  • tree[0] is the root and is never None.
  • Language types: Python list[int | None]; JavaScript an array of numbers and null; Java java.util.List<Integer> with null entries; C++ std::vector<std::optional<int>> with std::nullopt entries.

Rules

  • A node with value v satisfies the ordering condition when every value in its entire left subtree is strictly less than v and every value in its entire right subtree is strictly greater than v. An empty subtree imposes no condition.
  • Because both comparisons are strict, a tree in which two nodes hold the same value is never valid.
  • Return True if every node satisfies the condition and False otherwise (true / false in JavaScript, Java and C++). A single-node tree is valid.

Example 1

Input:  tree = [8, 3, 10, 1, 6, None, 14]
Output: True

The root 8 has left child 3 and right child 10; node 3 has children 1 and 6; node 10 has only a right child, 14. The root's left subtree holds {3, 1, 6}, all less than 8, and its right subtree holds {10, 14}, all greater than 8. Node 3 has 1 on its left and 6 on its right, and node 10 has 14 on its right, so every node satisfies the condition.

Example 2

Input:  tree = [8, 3, 10, 1, 9]
Output: False

The root 8 has children 3 and 10, and node 3 has children 1 and 9. Node 9 is greater than its parent 3, which is correct for node 3, but 9 lies in the root's left subtree and is not less than 8.

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.
  • Because of the encoding, tree holds at most 2 * 10^4 + 1 entries.

Examples

Example 1
Input
([-2147483648],)
Output
True
Notes
Minimum valid: a single node holding -2^31 is a valid tree.
Example 2
Input
([2147483647],)
Output
True
Notes
Minimum valid: a single node holding 2^31 - 1 is a valid tree.

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).

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def is_strict_bst(tree: list[int | None]) -> bool:
Sample call
is_strict_bst([-2147483648])
Language
Case 1
Input
([-2147483648],)
Expected
True
Case 2
Input
([2147483647],)
Expected
True

Browse More Questions

Show the approach

Approach

First rebuild the child links, then check each node against the open interval that its ancestors allow.

  1. Parse. Keep the created nodes in creation order, plus a pointer head to the next node whose child slots have not been read yet. Read two entries for each node, left then right. Each non-None entry becomes a new node, appended to the end. A None creates nothing, so it never gets child slots of its own, which is exactly the encoding rule. Fixed 2i + 1 / 2i + 2 indexing breaks as soon as a gap appears.
  2. Check. Walk the tree with an explicit stack of (node, lo, hi) triples. Start from the root with lo = -2^31 - 1 and hi = 2^31. A node fails if v <= lo or v >= hi. Its left child inherits (lo, v) and its right child inherits (v, hi).

Invariant: the interval a node carries is the intersection of the strict constraints from every ancestor. Being in an ancestor's left subtree means < ancestor, and being in its right subtree means > ancestor. Correctness: the tree is a strict BST exactly when every node meets the constraints of all its ancestors, which is the same as lying inside that interval. So the walk returns False at the first violation and True once every node has passed.

Edge cases: a single node is valid. The starting bounds sit just outside the 32-bit range, so values equal to -2^31 or 2^31 - 1 are accepted (Java and C++ keep the bounds in 64-bit types). Equal values always fail because both comparisons are strict. Trailing None entries are read and ignored. Because the stack is explicit, a chain 10^4 nodes tall causes no recursion-depth failure.

Time complexity:
O(n)
Space complexity:
O(n)