Solving Validate Binary Search Tree: Ensuring Proper Order

The "Validate Binary Search Tree" problem involves checking whether a binary tree meets the criteria of a binary search tree (BST). In a BST, the left subtree of a node contains only nodes with keys lesser than the node's key, and the right subtree only nodes with keys greater.

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

Example

Consider a binary tree:

This tree is a valid BST.

Solution Approach - Recursive Traversal

Breaking Down the Solution

• Recursive Strategy: The function validate recursively checks each node.
• Boundary Conditions: Each node's value is compared against the allowed range (low and high) determined by its ancestors.
• Left and Right Subtree Checks: Ensures that left child values are less than the node's value and right child values are greater.

Conclusion

Validating a binary search tree is a fundamental problem in tree algorithms, highlighting the importance of recursion and boundary conditions in tree traversal.

Rust Solution

Rust's Option<Box<TreeNode>> is what makes the tree representable at all: Box heap-allocates each child so the struct has a known size, while Option encodes the null link the TS version wrote as TreeNode | null. The match splits None and Some(n) as explicit arms, and if let Some(l) = low unwraps a bound only when one is present. The n.val as i64 widening cast is load-bearing — the bounds are typed Option<i64> rather than i32, so a node holding the extreme i32 values can still be compared against a strictly tighter limit without overflow. Recursion passes each subtree by reference (&n.left, and &root at the entry point) so the walk borrows the tree instead of moving it.

Go Solution

Go leans on *TreeNode pointers for the child links and reuses nil as both the empty-node marker and the absent-bound sentinel — the bounds are typed low, high *int, so low != nil guards each comparison before dereferencing with *low. Threading the next bound down is just &node.Val, taking the address of the node's own field rather than boxing or widening — plain int bounds, with none of the i64 cast the Rust side needs. The grouped low, high *int parameter declaration also collapses two same-typed pointers into a single spec.