Asked at
Validate Binary Search Tree
MediumVerifiedTreeDFSRecursion~20 min
Given the root of a binary tree, return whether it is a valid binary search tree.
A BST requires every node’s left subtree to hold strictly smaller values and its right subtree strictly larger values. A node is { val, left, right } with null children; the whole empty tree is null. The input arrives as the root node directly.
Examples
in{val:2, left:{val:1}, right:{val:3}}
outtrue
Left < root < right at every node.
in{val:5, left:{val:1}, right:{val:4, left:{val:3}, right:{val:6}}}
outfalse
3 sits in the right subtree of 5 but is less than 5.
Constraints
- 1 ≤ number of nodes ≤ 10⁴
- -2³¹ ≤ node.val ≤ 2³¹ - 1
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.