Validate Binary Search Tree
Properties and Validation DSA practice problem on Onlearn.
Difficulty: medium.
Topics: How can you determine whether a given tree is a Binary Search Tree (BST) or a general Binary Tree (BT)?, Binary Tree, Binary Search Tree, Traversal, In-order Traversal, Recursion, Time Complexity, Space Complexity, inorder traversal, range queries, binary tree, binary search tree, recursion, tree traversal, BST Properties.
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. Note: A single node tree is considered a valid BST. Input Specification: The binary tree is represented by its nodes. Each node has an integer val and pointers to its left and right children. A null pointer indicates no child. Output Specification: Return true if the given tree is a BST, false otherwise. Constraints: The number of nodes in the tree is in the range [0, 10^4]. 2^31 <= Node.val <= 2^31 1 Sample Test Cases: Example 1: Input: 2 / \ 1 3 Output: true Example 2: Input: 5 / \ 1 4 / \ 3 6 Output: false Explanation: The root node's value is 5. Its right child is 4, which is less than 5. This violates the BST property.