Binary Search Tree Validation

Determine if a given binary tree adheres to the rules of a Binary Search Tree (BST). This problem tests your understanding of tree traversals and BST properties, critical for many tree-based algorithms.

treebinary-treebinary-search-treerecursiondfs

Problem Statement

You are given the root of a binary tree. Write a function to determine if the tree is a valid Binary Search Tree (BST). A valid BST is defined as follows: for each node in the tree, all nodes in its left subtree must have values strictly less than the node's value, and all nodes in its right subtree must have values strictly greater than the node's value. This property must hold for all nodes in the tree.

Example 1

Input: A tree with root 10, left child 5, right child 15, left child of 15 being 11 and right child of 15 being 20

Output: True

The tree follows the BST property: 5 < 10 < 15, 11 < 15 < 20. Therefore, it's a valid BST.

Example 2

Input: A tree with root 8, left child 3, right child 10, left child of 3 being 1, right child of 3 being 6, left child of 10 being 4, right child of 10 being 14

Output: False

The tree does not follow the BST property because node '4' is in the right subtree of node '8', but 4 < 8. Also, node '4' is in the left subtree of node '10', but 4 < 10. This violates the BST property.

Constraints

-The number of nodes in the tree is in the range [1, 10000].
-The value of each node is in the range [-10000, 10000].
-The tree structure is a valid binary tree.

Brute Force Approach

The brute-force approach would involve checking every possible path in the tree to see if it violates the BST property. It's like manually checking every shelf in a library to ensure books are in the correct order, one by one. This is extremely inefficient, requiring you to compare each node with every other node in the tree.

TimeO(n^2)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem