Validate Binary Search Tree
Advanced
Validate Binary Search Tree
This challenge is all about validating whether a given binary tree is a Binary Search Tree (BST).
A Binary Search Tree is a tree where every node follows these rules:
- The left subtree of a node contains only nodes with values less than the node’s value.
- The right subtree of a node contains only nodes with values greater than the node’s value.
- Both left and right subtrees must also be binary search trees.
With these rules in mind, we will implement a function validate_bst that will take a binary tree node as input and return True if the tree is a valid BST and False otherwise.
Here is an example of the structure of a binary tree:
2 / \ 1 3
This tree is a BST because 1 < 2 < 3.
Examples
validate_bst({"value": 2, "left": {"value": 1, "left": None, "right": None}, "right": {"value": 3, "left": None, "right": None}}) # Output: True validate_bst({"value": 2, "left": {"value": 3, "left": None, "right": None}, "right": {"value": 1, "left": None, "right": None}}) # Output: False
Hint: Use recursion to check the left and right subtrees and ensure they meet the binary search tree conditions. Consider maintaining a range of valid values for each node.
Inputs
Arg 1:
{"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}Expected Output
trueActual Output