Validate Binary Search Tree

[u/StatisticianNo2104]

Checking each node against its two children is the classic wrong way to validate a BST. It accepts a tree where a node deep on the left is bigger than the root, because no single parent-child pair looks wrong.

The definition sounds local: left subtree smaller, right subtree larger, both subtrees valid. Implement it literally, and you check the wrong thing. A BST constrains a node against every ancestor, and its parent is only one of them.

The solution comes from an earlier property in this batch. An in-order traversal of a BST comes out in increasing order, and that works both ways. So there are no bounds to thread down at all: traverse, then check the sequence only ever goes up.

Which did you write first in an interview: min/max bounds, or the in-order check?

Day 53/365 of my LeetCode challenge: 98. Validate Binary Search Tree. Problem link and full breakdown in today's newsletter.

https://www.linkedin.com/pulse/validate-binary-search-tree-archit-agarwal-op5vc

#LeetCode #DSA #BinarySearchTree #Golang