Check that a tree is a valid search tree
DSA, Medium
Which structure or algorithm, and what does it cost.
A binary tree is a search tree when, for every node, all values in its left subtree are smaller than the node and all values in its right subtree are larger. Equal values are not allowed. You get the root of a binary tree. Each node has val, left and right, and left or right is null when absent. Return true if the tree is a valid search tree, and false if not. An empty tree (root is null) is valid.
Examples
Input tree level by level: 8 / (4, 12) / (2, 6, 10, 14)
Output true
Why Every node is larger than everything on its left and smaller than everything on its right.
Input tree level by level: 8 / (4, 12) / (-, -, 7, 14)
Output false
Why 7 is the left child of 12, so it is right of 8, but 7 < 8. Each parent-child pair looks fine; the rule fails further up.
Input tree: 5 with a left child 5
Output false
Why Edge case: equal values are not allowed.
Constraints
- 0 <= number of nodes <= 100,000.
- Each value is a whole number between -2,147,483,648 and 2,147,483,647.
- The tree can be very deep (all nodes in one chain).
- Do not change the tree.
Your answer must contain
- The approach in words, and why checking only each parent and child is not enough
- Code or pseudocode in any language
- Time and memory cost, with the reason (think of a deep tree)
- A hand trace of example 2 that shows where it fails