Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Given a binary tree, check if it is a binary search tree (BST). A valid BST does not have to be complete or balanced.

Consider the below definition of a BST:

- All nodes values of left subtree are less than or equal to parent node value
- All nodes values of right subtree are greater than or equal to parent node value
- Both left subtree and right subtree must be a BST
- By definition, NULL tree is a BST
- By definition, trees having a single node or leaf nodes are BST.

**Example One**

Input:

Output: false

Left child value 200 is greater than the parent node value 100; violates the definition of BST.

**Example Two**

Input:

Output: true

**Notes**

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: Return true if the input tree is a BST or false otherwise

Constraints:

- 0 <= number of nodes <= 100000
- -10^9 <= values stored in the nodes <= 10^9
- Return value must be boolean

We provided two solutions, both are optimal in terms of time and space complexity, though algorithms are different.

In the following three examples, tree A and B is a BST, where tree C is not:

In other_solution.cpp we use the definition of BST quite literally. For every node, recursively, we check that all values in the left subtree are <= current node value and all values in the right subtree are >= current node value. We also propagate all the "<=" and ">=" conditions down the recursion tree (they get more specific, more narrow as we go down the tree), effectively forming a valid range for every node we check. For example, in the following tree,

the requirements for X are both X>=1 and X<=4. Further, valid range for Y is Y>=X and Y<=4. Notice that because X>=1 holds true (X is checked before Y, higher up in the recursion tree), the effective valid range for Y is narrower than one for X; that way the range gets narrower as we go deeper down the tree. For better understanding please look at the solution.

**Time Complexity:**

O(*n*) where *n* denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the node value lies within a range or not, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate n + (n-1) → 2n-1 times can be represented as O(n) complexity.

**Auxiliary Space:**

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

**Space complexity:**

O(*n*).

In optimal_solution.cpp solution we have used in-order traversal property of a BST to validate whether it is a BST or not. If we store the values in an array during in-order traversal, it will be a sorted array if the given tree is BST. To check if an array is sorted or not, we just need to compare an element with the previous element of the array. We can do this while traversing the tree instead of storing the values in an array which will reduce space complexity. To achieve this, we have used a variable which stores the last visited nodes value at any time. So, when we are in a node, we can compare if the current node value is greater or equal to the previous node value. If this condition fails for any node then the given tree is not a BST. Otherwise it is.

**Time Complexity:**

O(*n*) where *n* denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the current node value is greater or equal to the previous node value, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate n + (n-1) → 2n-1 times can be represented as O(n) complexity.

**Auxiliary Space:**

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

**Space Complexity:**

O(*n*).

Note: Input and Output will already be taken care of.