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 theNone
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 BinaryTreeâ€¦
We will understand the code with this example:
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 asmax_l
is None 
min_r is None or node.key < min_r
will be True asmin_r
is None
We will getis_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â€¦
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
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 PaperPen approach and you will definitely understand thisâ€¦
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â€¦
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.
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