Is It a Search Tree?
MediumTrees
Problem
A data import produced a binary tree that is supposed to be a binary search tree. Check it.
The tree is valid when, for every node, all values in its left subtree are strictly smaller than the node's value and all values in its right subtree are strictly larger. Duplicates are therefore invalid. An empty tree is valid. Return true or false.
Example 1
- Input:
- root = [5, 3, 8, 1, 4]
- Output:
- true
Example 2
- Input:
- root = [5, 3, 8, 1, 6]
- Output:
- false
6 is the right child of 3, which is fine locally, but it sits in the left subtree of 5 and 6 > 5.
Example 3
- Input:
- root = [2, 2]
- Output:
- false
Equal values are not allowed.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -2^31 ≤ node.val ≤ 2^31 - 1
Hint
Show the first hint
Checking each node only against its own children is not enough. Why?
Walkthrough
How to approach it
01Clarify before coding
- Are duplicates allowed anywhere? No: strict inequality on both sides.
- Is an empty tree valid? Yes.
- Can values reach the 32-bit limits? Yes, so do not use ±2^31 as sentinels; use 'no bound' instead.
02Brute force
For every node, scan its entire left subtree for the maximum and its right subtree for the minimum and compare.
Cost: O(n²) time in the worst case (a chain), because each subtree is rescanned for every ancestor.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.