Validate Binary Search Tree With Python

The Prompt

Each BST node has an integer value, a left child node, and a right child node.

A node is valid if it satisfies the BST property: its value is greater than every node to it’s left, and its value is less than every node to its right.

The Code

Now, the validateBst function takes in only a tree as its input, but the logic behind the validation requires a minimum and maximum value, to act as pointers. Therefore, we’ll create a helper function that will take in the parameters we need in order to get our final solution. Let’s start.

The beginning logic can go as the following:

  • if there is no Tree, return TRUE
  • if the tree’s value is less than the minimum value (minVal) OR is greater than the maximum value (maxVal), then return FALSE

Below is an example of how the code in the helper function should look like so far.

Now, we can create a variable that will act as checker for the left value, then apply the same logic to check the right value. This can be done using recursion.

Now that the helper function is complete, simply invoke the helper function in our initial validateBst function, and the solution is complete. The final code should look like the following:

Complexity Analysis

The space complexity of this solution will be O(d) space, where (d) is the depth of the BST, since we’re using recursion and applying the helper function to each of the child nodes.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store