Skip to content
BASA DSA

Validate Binary Search Tree

MediumTrees

Return whether a binary tree is a strict binary search tree: every left descendant must be smaller and every right descendant larger than its ancestor.

Example 1

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 4, node 1: 2, node 2: 6, node 3: 1, node 4: 3, node 5: 5, node 6: 7. Edges: node 0 (4) — node 1 (2) left child; node 0 (4) — node 2 (6) right child; node 1 (2) — node 3 (1) left child; node 1 (2) — node 4 (3) right child; node 2 (6) — node 5 (5) left child; node 2 (6) — node 6 (7) right child.4261357
Argument 1 tree: level-order input; omitted children are null.

Input
root = [4,2,6,1,3,5,7]
Output
true

Explanation

Every left descendant is smaller than its ancestors and every right descendant greater.

Example 2

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 5, node 1: 1, node 2: 7, node 3: 4, node 4: 8. Edges: node 0 (5) — node 1 (1) left child; node 0 (5) — node 2 (7) right child; node 2 (7) — node 3 (4) left child; node 2 (7) — node 4 (8) right child.51748
Argument 1 tree: level-order input; omitted children are null.

Input
root = [5,1,7,null,null,4,8]
Output
false

Explanation

4 is in root 5's right subtree and violates its bound despite being below parent 7.

Example 3

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 2, node 1: 2. Edges: node 0 (2) — node 1 (2) left child.22
Argument 1 tree: level-order input; omitted children are null.

Input
root = [2,2]
Output
false

Explanation

A child equal to its parent violates strict inequality.

Constraints

  • 1 <= number of nodes <= 10000
  • Values are signed 32-bit integers

Function contractisValidBSTArguments: tree
Loading draft…
SolutionRuns on your device