Check if a binary tree is binary search tree or not - YouTube

In this lesson, we're going to solve a simple problem on binary tree

which is also a famous programming interview question,

and the problem is given a binary tree

we need to check if the binary tree is a binary search tree

are not. As we know a binary tree is a tree

in which each node can have atmost two children.

All these trees that I have drawn here are binary trees,

but not all of them are binary search trees. Binary search tree,

as we know is a binary tree in which for each node

value of all the nodes in left subtree is lesser

and if you want to allow duplicates we can say lesser or

equal and value of all the nodes in right subtree

is greater. We can define binary search tree as

a recursive structure like this. Elements in left subtree must be lesser or equal

and elements in right subtree must be greater and this should be true for all

nodes and not just a root node,

so left and right subtrees should themselves also be binary search trees.

Of these binary trees that I'm showing here,

A and C are binary search trees but B

and D are not. In B for the root node with value 10,

we have 11 in its left subtree which is greater than 10

and in a binary tree for any node all values in its

left subtree must be lesser. In D we are good for the root node.

The value in root node is 5 and we have

1 in left subtree which is lesser and we have 8, 9 and 12

in right subtree which are greater. So we are good for the root node

but for this node with value 8, we have 9

in its left. So this tree is not a binary search tree.

So how should we go about solving this problem. Basically,

I want to write a function that should take pointer or reference to root

node of a binary tree as argument and function should return true

if the binary tree is BST, false otherwise.

This is how my method signature look like in C++.

In C, we do not have boolean types so

return type here can be int. We can return

1 for true and 0 of false.

I'll also write the definition of node here.

For a binary tree node would be structure

with 3 fields, 1 to store data and 2

to store addresses of left and right children. In my definition of node here,

data type is integer

and we have 2 pointers to node to store addresses of

left and right children. Okay coming back to the problem

there are multiple approaches and we're going to talk about

all of them. The first approach that I'm going to talk about

is easy to think of but it's not so efficient

but let's discuss it anyway. We are saying that for a binary tree to be called

binary search tree,

it should have recursive structure like this. For the root node

all the elements in left subtree must be lesser or equal

and all the elements in right subtree must be greater, and left and right

subtrees

should themselves also be binary search trees. So let's just check for all of this.

I'm going to write a function named IsSubtreeLesser

that will take address of root node of a binary tree

or subtree and and integer value

as argument and this function will return true if

all the elements in the subtree are lesser so than this value

and similarly I'll write another function named IsSubtreeGreater

that will return true if all the elements in a subtree

are greater than the given value. I had just

declared this functions. I'll write body of these functions later.

Let's come back to this function IsBinarySearchTree.

In this function, I am going to say that if all elements in left subtree are

lesser and I'll verify this by making a call to IsSubtreeLesser function

passing it

address of left child of my current root.

Left child would be the root of current subtree and the data in root.

This function will return true if all the elements in left subtree

would be lesser than the data in root. Now the next thing that I want to check

for is

if elements in right subtree are greater than the data in root or not.

These two conditions are not sufficient. We also need to check if left

and right subtrees are binary search trees are not.

So I'll add two more conditions here have made a recursive call to

IsBinarySearchTree function passing it address of left child

and I have made another call passing address of right child

and if all these four function call IsSubtreeLesser, IsSubtreeGreater

and IsBinarySearchTree for left and right subtrees

return true if all these four checks pass then

our tree is a binary search tree. We can return true

else we need to return false. There is only one thing that the a missing in

this function now.

We are missing the base case. If the route is null that is

if the tree or subtree is empty, we can return true.

This is the base case for our recursion where we should stop.

With this much of code IsBinarySearchTree function is complete

but let's also write IsSubtreeLesser and ItsSubtreeGreater

functions because they are also part of our logic.

This function has to be a generic function that should check

if all the elements in a given tree are lesser than

a given value or not. We will have to traverse the complete

tree or subtree and see value in all nodes and compare

these values against this given integer. I'll first handle the base case in

this function.

If the tree is empty, we can return true else we need to check if the data in

root

is less than or equal to the given value and we also need to recursively check if

left and right subtrees of the current root have

lesser value or not. So I'm adding two more conditions here.

I'm making two recursive calls one for the left subtree and

another for the right subtree. If all these three conditions are true

then we are good else we can return false. IsSubtreeGreater function will

be very similar.

Instead of writing these two functions IsSubtreeLesser

and IsSubtreeGreater, we could also do something like this.

We could find the maximum left subtree

and compared it with the data in root, if maximum of a subtree is lesser

then all the elements a lesser and similarly if the minimum of

a subtree is greater all the elements had greater.

For the right subtree, we could find a minimum. So instead of writing these two

functions IsSubtreeLesser

and IsSubtreeGreater, we could write something like find max

and find min and this would also fit.

So this is a solution using one of the approaches.

Let's quickly run this code on an example binary tree and see how it will execute.

I have drawn a very simple binary tree here which actually is a binary search

tree.

let's assume some addresses for these nodes the tree.

Let's say the root node is that address 200 and

I'll assume some random addresses for other nodes as well.

To check if this binary tree is a binary search tree or not,

we will make a call to IsBinarySearchTree function.

I'm writing IBST here as Shortcut for IsBinarySearchTree

because I'm short of space here. So I'll make a call to this function

maybe from the main function passing addressed 200,

address of the root node. For this function call

address in this local variable address collected in this local variable root

will be 200. Root is not null.

Null is only a macro for address 0.

For this call root is not null, so we will not return true at this line.

We will go to the next if. Now here, we will make a call to

IsSubtreeLesser function. Arguments passed will be address

of left child which is 150 and

7 the data in node at 200.

Execution of the calling function will pause and

will resume only after the called function returns.

Now in this call to IsSubtreeLesser, root is not null so

we will not return true at first line. We will go to the next

if. Now here the first condition is if

data in root this time

is 150 because on this call is for this left subtree

and for this left subtree address of root is 150.

Data in root is 4 which is lesser than

7, so the first condition is true and we can go to the second condition which is

a recursive call.

This call will pause and we will go to the next call.

Here once again the data in node

at 180, 1 is lesser than 7

so first condition is true and we will make

recursive call. Left subtree for node at 180

is null. There is no left child so

we will return at first line. Root is null this time.

This particular call will simply to return true. Now in this previous call when

root is 180,

second condition for if is also true. So

we will make another call for right subtree. Once again address passed

will be 0 and we will simply return true and now for this call

IsSubtreeLesser 187, all three conditions are true.

So this guy can also return true and now ISL 150,7 will resume.

Now this guy will make a recursive call for the right subtree

and this guy after everything will also return true.

Now for this call because all 3 conditions in the if statement are true,

this guy will also return true and now IsBinarySearchTree function will

resume.

For this call we have evaluated the first condition

we have got true now this guy will make another call

to IsSubtreeGreater, passing address of right child and value 7.

This guy after everything will return true and now we will have 2 recursive

calls,

to check if left and right subtree are binary search trees on not.

We will first have a call for the left subtree.

The execution will go on like this but I want you to see something.

Each call to binary search tree function,

we are comparing the data in root with all the elements in left subtree and

then all the elements in right subtree.

This example tree could be really large then in that case

in the first call IsBinarySearchTree for this complete tree,

we would recursively traverse this whole left subtree

to see whether all the values in this subtree

are less than 7 or not and then we will traverse all nodes in this right subtree

to see if values have greater than 7 or not and then

in next call IsBinarySearchTree, when we would be validating with this

particular subtree is BST or not.

We would recursively traverse this subtree if values are lesser than 4

or not

and this subtree to see if value so greater than 4 or not.

So all in all during this whole process there will be a lot of traversal.

Data in nodes will be read and compared multiple times.

If you can see all nodes in this particular subtree

will be traversed once in call to IsBinarySearchTree for 200.

When we will compare value in these nodes with 7

and then these nodes will once again be traversed

in call to IsBinarySearchTree for 150 when

they will be compared with 4. They will be traversed in call to

IsSubtreeLesser.

All in all these two functions IsSubtreeLesser

and IsSubtreeGreater very expensive. For each node, we are looking at all nodes in

its subtrees.

There is an efficient solution in which we do not need to compare

data in a node with data in all nodes in its

subtrees and let's see what the solution is.

What we can do is we can define a permissible

range for each node and data in that node must be in that range

we can start at the root node with a range

-infinity to infinity, because for the root node

there is no upper and lower limit and now as we are traversing we can set a range

for other nodes.

When we are going left, we need to reset the upper bound

so for this node at 150, data has to be between

-infinity and seven. Data in left child cannot be greater than data in

root.

If we're going right, we need to set the lower bound

for this node at 300 range would be 7 to infinity.

7 is not included in the range. Data has to be strictly greater than 7.

For this node at 180, the range will be -infinity to 4.

For this node with value 6 lower bond will be 4 and upperbound would be 7.

Now my code will go like this. My function IsBinarySearchTree will take

two more arguements,

an integer to mark lower bound or min value

and another integer to mark the upper bound or max value

and now instead of checking whether all the elements in left subtree are lesser than

the data in root

and all the elements in right subtree are greater than the date in root or not.

We will simply check whetheer data in root is

in this range or not. So I'll get rid of these two function call

IsSubtreeGreater

and IsSubtreeGreater which are really expensive and I'll

add these two conditions. Data in root must be greater than min value

and data in root must be less than max value. These two checks will take

constant time.

IsSubtreeLesser and IsSubtreeGreater functions were not taking

constant time.

Running time for them was proportional to number of nodes in the subtree.

Okay now these two recursive calls should also have two more arguements.

For the left child lower bound will not change,

upper bound will be to data in current node and for the right child, upper

bound will not change

and lower bond will be data in current node. This recursion looks good to me. We

already have to base case written.

The only thing is that the Caller of this IsBinarySearchTree function

may only want to pass the address of root node so what we can do is instead of

naming this function IsBinarySearchTree. We can name this function

as a utility function like IsBstUtil

and we can have another function name IsBinarySearchTree

in which we can take only to address of root node and this function can call

IsBstUtil to function passing address of root.

Minimum possible value in integer variable for -infinity

and maximum possible value in integer valuable for

+infinity INT_MIN and INT_MAX here are macros

for a minimum and maximum possible values in Int.

So this is a solution using second approach which is quite efficient.

In this recursion will go to each node once and at each node we will take

constant time

to see whether the data at node is in a defined range or not

and time complexity would be O(N) where N is number of nodes in the

binary tree.

For the previous algorithm, time complexity was O(N^2).

One more thing, in this code I have not handled

the case that Binary search tree can have duplicates.

I am saying that elements in left subtree must be strictly lesser and elements in

right subtree

must be strictly greater. I leave it for you to see how you will

allow duplicates. There is another solution to this problem.

You can perform in order traversal of binary tree

and if the tree is binary search tree you would read the data in

sorted order. In-order traversal of a

binary search tree gives a sorted list. You can do some hack

while performing in order traversal and check if you're getting the elements in

sorted order or not.

During the whole traversal you only need to keep track of

previously read node and at any time data in a node that you're reading

must be greater than the data in previously read node.

Try implementing this solution, it will be interesting. Okay I'll stop here now.

In cominng lessons, We will discuss some more problems on Binary tree.

Thanks for watching.