Python Binary Search Tree from a "Pro Coder" example

user_14074501 0
Viewed 77

So I was looking into an "Easy Python code example" that checks if a set of nodes form a Binomial tree or not, it should evaluate and return either True or False, the full code is the following:

class Node(object):
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.right = right
        self.left = left


class Solution(object):
    def _isValidBSTHelper(self, n , low, high):
        if not n:
            return True
        val = n.val
        if ((val > low and val < high) and
           self._isValidBSTHelper(n.left, low ,n.val) and
           self._isValidBSTHelper(n.right, n.val, high)):
           return True
        return False

    def isValidBST(self, n):
        return self._isValidBSTHelper(n, float('-inf'), float('inf'))


##        (_5_)
#       /        \
#   (_4_)        (_7_)
#  /     \      /     \
#(_3_) (empty)(_6_)   (_8_)

node = Node(5)
node.right = Node(7)
node.right.right = Node(8)
node.left = Node(4)
node.left.left = Node(3)
node.right.left = Node(6)
print(Solution().isValidBST(node))

The comments are supposed to be just a visual representation of the nodes that were expressed below.

I'm having a hard time understanding why is float('-inf'), float('inf') needed in

def isValidBST(self, n):
    return self._isValidBSTHelper(n, float('-inf'), float('inf'))

and how low, high, and n.val values function in

class Solution(object):
    def _isValidBSTHelper(self, n , low, high):
        if not n:
            return True
        val = n.val

Any help would be appreciated in understanding how does this code works, thanks

binary-search-tree python
2 Answers

First lets clarify what are the properties of a valid BST:

  • Each node has at most two children

  • The node's value is between its left child's ( if exists ) and right child's ( if exists )

    which means : left child value < node value < right child value

  • Also any null node is a valid BST in the trivial case.

Now you need to check these properties at each node, which is what the function is trying to achieve:

  • first it checks the trivial case of node is null - return true
  • Then it checks if the node's value is between a low and high value and then recursively checks for its left child and right child also, because the properties need to be valid at every node!

Now what would you initially pass the low, high values for the root ? You would pass the minimum value among all nodes as low and maximum value among all nodes as high, because the root node's value lies between them.

If you know before hand these minimum, maximum values you could pass those as low, high. But you don't know them ( well you can find out if you traverse - but its just a waste of time ), instead you can just pass the theoretical values of negative and positive bounds. Because you are sure the node's value will definitely be between those two.

user_14103030

The very first thing you should to is review the definition of a Binary Search Tree. All the questions you are asking are based on the constraints that the definition imposes.

First, consider an arbitrary BST. You don't know anything about it, except how it is structured. You're told that the keys are numbers, so you know that the comparisons are numeric comparisons.

So, what can you say about the root node? Nothing. You know it have a numeric key, but you don't know if the key is 1, or 0.0000000001, or 10000000000.

But there's this function that wants to constrain it, to check if it is less than some value and greater than some other value. If only there was some number that was greater than all other numbers... If only there was a number that was less than all other numbers...

To Infinity and Beyond!

And that is where float('inf') and float('-inf') come from. The coder has written a function that takes a "high" and a "low" value. But since the tree is arbitrary, we don't know enough to provide a meaningful value. So the coder either needs: a value that is higher than every other value; or a check in the code to avoid the test.

The test could be written like:

if high is not None and val < high:

But that's actually slowing things down, since presumably once we get inside the tree there will (nearly) always be a high and a low value. So instead, she used float('inf'), because that's "positive infinity," a value greater than all other values. (Except for Nan and maybe another positive infinity...)

Likewise for the low value and float('-inf'), which is negative infinity and lower than all numbers.

Bottom line, those numbers are cheats that are used before tree-specific data is available.

Recursive Constraints

Now consider these lines:

       self._isValidBSTHelper(n.left, low ,n.val) and
       self._isValidBSTHelper(n.right, n.val, high)):

In fact, let's get rid of the junk and consider just this:

       (n.left, low, n.val)
       (n.right, n.val, high)

The first (upper) recursive call uses the left node of the current node. Also known as the "left subtree". And it says, "everything in the (left subtree) must be greater than this low value that I am not touching, and also must be less than the current node value".

This goes back to the definition of a BST: everything in the left subtree must be less than the current node.

Likewise, the second (lower) recursive call doesn't change the high value, but says "everything in the right subtree must be greater than the current node value". Again, right out of the definition.

If you look at the diagram in the comments, you'll see that those infinity values propagate down the outer sides of the tree. But as soon as the code moves toward the center of the tree, both the high and low values will be taken from tree nodes, and they will be meaningful, concrete tests.

For example, 5 is checked with -Inf < 5 < +Inf, while 7 is checked with 5 < 7 < +Inf, but then 6 is checked with 5 < 6 < 7.

user_40290140
Related