2

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

Improve this question
4
  • 3
    The "helper" function is not very helpfully named or documented. :) What it's doing is checking to make sure that the subtree is both (a) internally valid and (b) entirely within the bounds given by low and high. That's why it starts at the root with the range -inf to inf. "Internally valid" means that the left subtree's values must all be smaller than the root, and the right subtree's values must all be larger. You pass the range down as you go into deeper subtrees to make sure that you're satisfying the bounds required by the various parent nodes. Commented Aug 9, 2020 at 20:23
  • @Samwise thanks for your answer, the only thing I'm still don't clearly get is how did the n variable got the val,right,left attributes, so it's aNode(object) or it's really refering to the node variable? Commented Aug 10, 2020 at 19:21
  • 1
    n is a Node object. This code would be easier to understand if it had type annotations in addition to better function/variable names! :) Commented Aug 10, 2020 at 19:41
  • Also according to the coder explanation the if not n: return True line just applies when there's no nodes, while in reality that line also "escapes" the iterations when a node doesn't have right nor left children , returning the value True. Just as a reference, this code was written by a guy that goes for the name "Techlead" on YT, but the Binary search tree one isn't on YT, it's on a site called "CoderPro",featured as the free sample of a series of training videos, if anybody else is interested in looking the source material and the coder explanation of this code. Thanks for your help Commented Aug 10, 2020 at 20:40

2 Answers 2

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thank you for your input, while I now understand how the function iterates through the whole tree,can I safely assume that the n variable points to the correct children Node(object) through the hierarchic attributes of the variable node? So i.e. when working with node.right then n.val, n.left, n.right becomes whatever it is stated or pointed in node.right.val, node.right.left, node.right.right
Yes. The n variable is just a parameter of the nested function, so whatever it gets called with in that slot will be accessed using n. It starts with passing the root of the tree into n, then recursively the left child node, ... etc.
1

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.