Validate Binary Search Tree

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

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Input: root = [2,1,3]
Output: true

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Approach : Iterative Inorder Traversal

Left -> Node -> Right order of inorder traversal means for BST that each element should be smaller than the next one.

Hence the algorithm with O(N) time complexity and O(N) space complexity could be simple:

• Compute inorder traversal list inorder.
• Check if each element in inorder is smaller than the next one.

Complexity Analysis

• Time complexity : O(N) in the worst case when the tree is BST or the “bad” element is a rightmost leaf.
• Space complexity : O(N) to keep stack.