Leetcode - Validate Binary Search Tree

Question

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.

This is atree question.

Idea(s)

• Using a DFS solution
• The idea here, is we want to validate the BST by validating that the left child is less than the current node and that the right child is greater than the current node and then call isValidBST or a helper function on the current nodes children recursively which will span the entire tree
• We should create a helper function isValidNode that accepts the current node, and a lower and upper boundary where one of the boundaries get updated with the current nodes value as we recursively call our helper function
• HERE, the DFS base case is node == None where we return true since if this check is successful, we will be able to propagate down the tree and back up with no issues
• Otherwise, if we run into an issue, return false and propagate the False back up the stack
• Then return the & of the recursive call to the two children

DFS Hints

Use “return” when you want to propagate information back up the stack

Solution