Discussion Related to Check Binary Tree

def removeNone(nums):
return [i for i in nums if i is not None]
def checkbst(node):
if node is None:
return True,None,None
bst_l,min_l,max_l=checkbst(node.left)
bst_r,min_r,max_r=checkbst(node.right)
is_bst=(bst_l and bst_r and (max_l is None or node.key>max_l) and(min_r is None or node.key<min_r))
min_key=min(removeNone([min_l,node.key,min_r]))
max_key=max(removeNone([max_l,node.key,max_r]))
return is_bst,min_key,max_key

def removeNone(nums):
    return [i for i in nums if i is not None]

def checkbst(node):
    if node is None:
        return True, None, None
    
    bst_l, min_l, max_l = checkbst(node.left)
    bst_r, min_r, max_r = checkbst(node.right)
    
    is_bst = ( bst_l and bst_r and 
               (max_l is None or node.key > max_l) and 
               (min_r is None or node.key < min_r)
             )
    min_key = min(removeNone([min_l, node.key, min_r]))
    max_key = max(removeNone([max_l, node.key, max_r]))

    return is_bst, min_key, max_key

First let’s get removeNone function out of the way.
This function is only taking a list and removing all the None values, for example if we give this function a list → [1, None, 2, None, None, 3, 4, None]
It will return a list → [1, 2, 3, 4]
Hope it’s Clear…Now to the main Function…

As the name suggests checkbst function checks if the given tree is Binary Search Tree or not, also Here we get the minimum and maximum value in the given Binary-Tree…

We will understand the code with this example:
image

We will call checkbst passing it the root Node which is 2 here…
Now the function first of all will check if the passed node is some node or not (i.e. if it’s None)
In our case it is not None as we have passed root Node 2 which is actually a Node object…

So, after this checkbst will be called on the left Node which is 1…

  • Here the Checking of None is False, so…

    • checkbst will be called on left of 1 which is None…so, this will return True, None, None
      becasue a None node is a Binary Search Tree with max and min element as None…
    • checkbst will be called on right of 1 which is None…so, this will also return True, None, None

    So, for Node 1, the conditions

    • bst_l and bst_r will be True
    • max_l is None or node.key > max_l will be True as max_l is None
    • min_r is None or node.key < min_r will be True as min_r is None
      We will get is_bst as True

    Now min_key will be calculated which would be 1 as min_l and min_r are both None and after removing these we would be left with 1
    Same goes for max_key…

    We will return True, 1, 1

Now we get bst_l, min_l, max_l for Node 2 as True, 1, 1
So, Now checkbst will be called on the right Node which is 3…

  • The Process for this Node would be same as Node 1…but here we will return True, 3, 3

So, we get bst_r, min_r, max_r for Node 2 as True, 3, 3

Now checkbst will be calculated…

  • bst_l and bst_r would be True as Both contains True
  • max_l is None or node.key > max_l would return True as node.key is 2 and max_l is 1 and node.key > max_l
  • min_r is None or node.key < min_r would return True as node.key is 2 and min_r is 3 and node.key < min_r

So is_bst will be True
Now max_key and min_key would be calculated…

  • minimum value among (min_l, node.key, min_r) would be 1 as
    min_l → 1, node.key → 2, min_r → 3
  • maximum value among (max_l, node,key, max_r) would be 3 as
    max_l → 1, node.key → 2, max_r → 3

So, The function would finally return True, 1, 3

Now let’s go through the function with this Example…
image

Here checkbst would be called on Node(3)…

  • After this checkbst would be called on Node(1) which would return True, 1, 1
  • Now checkbst would be called on Node(2) which would return True, 2, 2

Now is_bst will be calculated…

  • bst_l and bst_r would be True
  • max_l is None or node.key > max_l would return True as node.key is 3 and max_l is 1 and node.key > max_l
  • min_r is None or node.key < min_r would return False as node.key is 3 and min_r is 2 but node.key > min_r

So, is_bst would be False
Now min_key and max_key would be calculated…

  • minimum value among (min_l, node.key, min_r) would be 1 as
    min_l → 1, node.key → 3, min_r → 2
  • maximum value among (max_l, node,key, max_r) would be 3 as
    max_l → 1, node.key → 3, max_r → 2

So, The function would finally return False, 1, 3

Hope it Helps…

P.S.
I am not quite gettiing What you are asking in second part of your question as there is no variable named is_bst_l

2 Likes

you said Now we get bst_l, min_l, max_l for Node 2 as True, 1, 1 but How it just happened??
How did min_1 which is None and max_l which is None all of a suddent become 1 and 1 ??

min_l and max_l does not become 1 and 1 all of a sudden…there is a logical explanation …

You see…when check_bst was called on left node (1) …it was again called on it’s left node which is None and again on its’s right node which is also None…

So now the condition was evaluated which is

( bst_l and bst_r and 
 (max_l is None or node.key > max_l) and 
 (min_r is None or node.key < min_r)
)

and for left node (1) these values are:
bst_l → True
bst_r → True
max_l → None
min_r → None
node.key → 1

after evaluation is_bst is True

Now in the next line min_key is calculated by:

min_key = min(removeNone([min_l, node.key, min_r]))

Now the values are:
min_l → None
node.key → 1
min_r → None

So after removing all Nones we are left with only 1 so min_key = 1

Similarly for max_key

max_key = max(removeNone([max_l, node.key, max_r]))

values are:
max_l → None
node.key → 1
max_r → None

So we get max_key = 1

And that is How min_l and max_l become 1 and 1 for the root node 2 before the evaluation of node (3)

Hope you Understand…
I didn’t get into much detail and depth as I think I have explained this concept in the previous post in much depth and detail…
So please go through it line by line using a Paper-Pen approach and you will definitely understand this…

1 Like

But
min_key is not min_l
max_key is not max_l

there is no code we are assigning min_l = min_key and max_l = max_key

Hey…

After getting min_key = 1 and max_key = 1 we are returning the
tuple is_bst, min_key, max_key to the parent node

So for node(2) when we called…

bst_l, min_l, max_l = checkbst(node.left)

our checkbst(node.left) returned True, 1, 1

so overall we get…

bst_l, min_l, max_l = True, 1, 1

here min_l and max_l are assigned the values 1 and 1

Hope it’s clear…
I would suggest watching some content regarding Binary Search trees on Youtube and also some videos related to recursions to get the idea what’s happening and let me tell you it is easy to grasp once to get in the habit but it quite hard in the beginning for almost everyone…

Some Youtube videos…

Hope it helps…
I have watched all these videos previously when I was a beginner and I can assure you they will help you…

bro check this, please call me +918465854161 please

there is nothing checkbst(node.left) or checkbst(node.right) is returning other than True, None, None and it is very clearly stated in the code

Hey…
Who is saying that checkbst(node.left) or checkbst(node.right) is returning only True, None, None

We can clearly see that if the Base is encountered then only we are returning True, None, None otherwise we are returning…is_bst_node, min_key, max_key in the very last line of the code that you have sent the picture of…

You can also see in the right picture that min_l and max_l are getting some values which are then returned to the parent node…

I think you are having confusion somewhere in the recursion
Maybe watch some lectures regarding recursion problems and then maybe you would understand.
Hope it helps…

I would recommend not sharing personal information like numbers in the public forum…if you want you can message me personally…to share numbers and all that stuff…
You can also join Discord if you want…

I want to know users was a list of names then how it is assigned to the class users and now it holds whole individual user HOW???

users variable is not a list of names, it’s a list of objects of User class.

1 Like

Hi I have a doubt can someone tell why we are using

  • node.left= TreeNode.parse_tuple(data[0])
    and
    -node.right = TreeNode.parse_tuple(data[2])

why we are doing this as in
when we are doing this without class we are simple calling
node.left=parse_tuple(data[0])

can someone tell ?

def tree_height(node):
if node is None:
return 0
return 1 + max(tree_height(node.left), tree_height(node.right))
here in return how max will return .those are not numbers and also they are values of nodes how it will give height

TreeNode is class function only
before node.left= TreeNode.parse_tuple(data[0])
we had defined node=TreeNode(data[1]) which is class function

you can see the height is calculated from bottom to up
the output is like below where each iteration the sum of left and right
0 2
0 3
0 1
1 1
2 3
0 5
0 3
0 4
1 4
2 3
0 7
0 6
1 6
0 8
1 8
2 7
3 5
4 2
4

additional visual example example: