# 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:

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â€¦

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â€¦

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.

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