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.

Geek
Inputs

Arg 1:

{"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}
Expected Output
true
Actual Output
Validate Binary Search Tree [advanced] | Coding for Kids