1
00:00:00,750 --> 00:00:03,090
Hi everyone, let's do this question.

2
00:00:03,090 --> 00:00:06,030
You are given the root of a binary tree.

3
00:00:06,240 --> 00:00:09,330
Determine if it is a valid binary search tree.

4
00:00:09,360 --> 00:00:12,300
A valid binary search tree is defined as follows.

5
00:00:12,300 --> 00:00:17,820
The left subtree of a node contains only nodes with keys less than the nodes.

6
00:00:17,820 --> 00:00:18,330
Key.

7
00:00:18,330 --> 00:00:23,190
The right subtree of a node contains only nodes with keys greater than the nodes key.

8
00:00:23,190 --> 00:00:27,360
Both the left and right subtrees must also be binary search trees.

9
00:00:27,360 --> 00:00:29,850
So this is a question we are dealing with now.

10
00:00:29,850 --> 00:00:35,760
Again, remember in binary search tree questions, it's important how the binary search tree is defined.

11
00:00:35,760 --> 00:00:41,880
In a previous question, we defined the BST such that the left has to be strictly less, but the right

12
00:00:41,880 --> 00:00:44,760
was greater than or equal to the value of the node.

13
00:00:44,760 --> 00:00:48,360
So that's how we defined the binary search tree in a previous question.

14
00:00:48,360 --> 00:00:54,030
Now over here in this question it's defined that the left has to be strictly less and the right value

15
00:00:54,030 --> 00:00:58,950
has to be greater than strictly greater than the node's key value or the node's value.

16
00:00:58,950 --> 00:01:00,000
So this is important.

17
00:01:00,000 --> 00:01:00,420
All right.

18
00:01:00,420 --> 00:01:04,890
Now again remember what we have to do is we will be given the root of a binary tree.

19
00:01:04,890 --> 00:01:08,010
And we have to check whether it is a valid binary search tree.

20
00:01:08,010 --> 00:01:12,690
So that's the question now in the interview, if you are getting this question always, you have to

21
00:01:12,690 --> 00:01:18,180
ensure that you ask sufficient clarifying questions so that you are very thorough with what the expectation

22
00:01:18,180 --> 00:01:18,330
is.

23
00:01:18,330 --> 00:01:21,510
And you, you have no doubt about any edge case, etc..

24
00:01:21,510 --> 00:01:26,760
Now, a good question that you could ask over here is will there be duplicate values in the binary tree?

25
00:01:26,760 --> 00:01:31,020
So whenever you're dealing with binary search trees, this is going to be a question that is going to

26
00:01:31,020 --> 00:01:31,740
be important.

27
00:01:31,740 --> 00:01:33,750
The case about duplicate values.

28
00:01:33,750 --> 00:01:36,570
Now over here because it's defined in this manner.

29
00:01:36,570 --> 00:01:39,960
That is the left value has to be less than the node's value.

30
00:01:39,960 --> 00:01:42,900
And the right value has to be greater than the node's value.

31
00:01:42,900 --> 00:01:48,330
Therefore, let's say the interview over here replies to you that yes, there can be duplicate values,

32
00:01:48,330 --> 00:01:53,790
but in that case the binary tree is not a valid binary search tree.

33
00:01:53,790 --> 00:01:54,360
All right.

34
00:01:54,360 --> 00:01:57,240
Now let's go ahead and write a few test cases.

35
00:01:57,840 --> 00:02:03,300
Now remember in the interview you can always ask the interviewer if he or she is okay with coming up

36
00:02:03,300 --> 00:02:04,830
with test cases together with you.

37
00:02:04,830 --> 00:02:09,690
So that will help solidify your understanding of the question, and you will be very thorough with what

38
00:02:09,690 --> 00:02:10,710
the expectation is.

39
00:02:10,710 --> 00:02:11,940
That's a good practice.

40
00:02:11,940 --> 00:02:14,490
Now over here, let's go ahead and write a few test cases.

41
00:02:14,490 --> 00:02:17,880
Let's say the binary tree which is given to us is this one over here.

42
00:02:17,880 --> 00:02:23,520
So in this case you can see that we would have to return false because this value over here has to be

43
00:02:23,520 --> 00:02:25,740
less than the value over here.

44
00:02:25,740 --> 00:02:25,920
Right.

45
00:02:25,920 --> 00:02:29,730
Because you can see the left value has to be less than the node's value.

46
00:02:29,730 --> 00:02:31,140
So that was what is mentioned.

47
00:02:31,140 --> 00:02:33,270
And that's the binary search tree property.

48
00:02:33,270 --> 00:02:34,590
So this is clearly false.

49
00:02:34,590 --> 00:02:40,020
Now if the tree with the binary tree which is given to us is this one over here, then also it's going

50
00:02:40,020 --> 00:02:44,670
to be false because this value over here has to be greater than the value which we have over here.

51
00:02:44,670 --> 00:02:45,780
And that's not the case.

52
00:02:45,780 --> 00:02:45,960
Right.

53
00:02:45,960 --> 00:02:48,060
So over here also we have to return false.

54
00:02:48,060 --> 00:02:49,770
Now let's take another case.

55
00:02:50,280 --> 00:02:53,760
Let's say the binary tree which is given to us is this one over here.

56
00:02:53,760 --> 00:02:59,940
Now we see that we have ten as the root node and we have six over here towards its left which is less

57
00:02:59,940 --> 00:03:00,660
than ten.

58
00:03:00,660 --> 00:03:01,470
So that's correct.

59
00:03:01,470 --> 00:03:05,040
And we have 30 towards its right which is greater than ten.

60
00:03:05,040 --> 00:03:06,120
So that's also correct.

61
00:03:06,120 --> 00:03:08,940
And we have one over here which is less than six.

62
00:03:09,030 --> 00:03:09,780
So that's correct.

63
00:03:09,780 --> 00:03:12,480
And we have 20 over here which is greater than six.

64
00:03:12,480 --> 00:03:19,110
But this will not be correct because whatever comes to the left of this node has to be less than ten.

65
00:03:19,110 --> 00:03:19,380
Right.

66
00:03:19,380 --> 00:03:24,630
So because 20 is not less than ten that's why we have to return false in this case.

67
00:03:24,630 --> 00:03:28,440
So it's not enough just to check whether the left or over here.

68
00:03:28,440 --> 00:03:28,650
Right.

69
00:03:28,650 --> 00:03:31,200
For this particular node the left and right is correct.

70
00:03:31,200 --> 00:03:34,410
But you cannot have 20 at all on the left of ten.

71
00:03:34,410 --> 00:03:37,350
So that's why this in this case we would have to return false.

72
00:03:37,350 --> 00:03:42,270
Now in a similar case, if this is the binary tree which is given to us, we would have to return false

73
00:03:42,270 --> 00:03:45,930
because over here we cannot have any value which is less than ten.

74
00:03:45,930 --> 00:03:46,170
Right.

75
00:03:46,320 --> 00:03:50,520
So any value towards the right of this node has to be greater than ten.

76
00:03:50,520 --> 00:03:53,340
So again because of this node we will have to return false.

77
00:03:53,340 --> 00:03:59,490
Now if we are given a binary tree with only one node which is the root itself, then we would have to

78
00:03:59,490 --> 00:04:02,130
return true because that's a valid binary search tree.

79
00:04:02,130 --> 00:04:07,260
And then if the root itself is null, we will have to return true, because this is also considered

80
00:04:07,260 --> 00:04:08,730
a valid binary search tree.

81
00:04:08,730 --> 00:04:12,450
Again, you can confirm this with the interviewer when you come up with test cases.

82
00:04:12,450 --> 00:04:14,130
So we have understood the question.

83
00:04:14,130 --> 00:04:18,270
Now in the next video let's go ahead and think how we can solve this question.