Check for BST

Problem Statement

Given a binary tree, we have to determine if the tree is a binary search tree or not. A tree is said to be a valid binary search tree when,

• All the nodes in the left subtree are less than the parent node
• All the nodes in the right subtree are greater than the parent node.
• Also, the left and right subtrees have to satisfy the binary search tree conditions.

Example

consider the following examples example-1

                3
               / \
              2   5
             / \   \
            1   4   6

output:

example-2

                4
               / \
              2   5
             / \   \
            1   3   6

output:

Example Explanation

In example 1, Condition 1 is not satisfied. All the nodes in the left subtree have to be less than the parent node, but 4 is not less than 3. Hence, it's not a binary search tree

In example 2, Condition 1 is satisfied, where all the nodes in the left subtree are less than the parent node. Similarly, condition 2 is satisfied, where all the nodes in the right subtree are greater than the parent node. And condition 3 is satisfied, where both left and right subtrees have fulfilled the bst conditions.

Constraints

The constraints we are going to follow for the below implementations are,

• Given tree can have any number of edges between $0$ and $10000$ (both inclusive).
• Each node can have any value between $-2^{31}$ and $2^{31}-1$ (both inclusive).

Approach 1- Brute Force Approach

The idea is to check if all the nodes in the left subtree are less than the parent node and if all the nodes in the right subtree are greater than the parent node for all the nodes in the tree.

Now instead of checking for all nodes in the left and right subtrees, we can compare the parent node with max in the left subtree, and min in the right subtree.

Algorithm

The algorithm to check for the bst follows as for each node in the tree,

• Find the max of all the nodes in the left subtree, and check if the max is less than the current node.
• Find the min of all the nodes in the right subtree, and check if the min is greater than the current node.
• Validate if both left and right subtrees satisfy the bst conditions.

Code Implementation

The java implementation of brute force approach to check for bst follows as

Output:

C++ implementation of brute force approach to check for bst follows as

Output:

Python implementation of brute force approach to check for bst follows as

Output:

Time Complexity

For each node, we are fetching the maximum of the left subtree and the minimum of the right subtree. The time required to find the minimum or maximum of a tree is O(N). Since we are doing it for each node and fetching both minimum and maximum, the time complexity will be N*O(N+N) i.e., O(N^2).

Space Complexity

This approach doesn’t use any auxiliary space, but it internally maintains a recursion stack of size H(height of tree) for checking bst and getting min functions. So the space complexity will be O(H).

Approach 2 - Using Upper and Lower Limits

The idea is to remove the getMin and getMax methods by adding lower and upper limit parameters in the function and check if the current node falls under the expected range. And one of the boundaries of the range gets narrowed in the further recursive calls to validate if the left and right subtrees satisfy the bst conditions.

Algorithm

The algorithm for the recursive approach follows as

• Add the parameters left and right along with root in the function.
• Check if the current node value falls between left and right.
• Traverse to left subtree by updating the right boundary to current node value.
• Traverse to right subtree by updating the left boundary to current node value.

Implementation

The java implementation for the above approach to check for bst follows as

C++ implementation for the above approach to check for bst follows as

Python implementation for the above approach to check for bst follows as

Output:

Time Complexity

This approach has to visit each node in the tree and validate if the value falls under the expected range. So the time complexity will be O(N).

Space Complexity

This approach doesn’t require any auxiliary space, but it internally maintains a recursion stack of size H(height of binary tree). So the space complexity will be O(H).

Approach 3 - Using Inorder Traversal

One of the interesting properties of a binary search tree is that if we flatten the tree or consider the inorder traversal of the tree, the series will be in ascending order. Now one of the ways is to perform inorder traversal and check if the obtained array is sorted or not. But we can validate this during the inorder traversal itself.

The idea is to maintain a prev pointer and check if the next node in the inorder traversal is greater than the prev node or not.

Algorithm

The algorithm for the recursive inorder approach follows as

• Maintain a prev node and initialize it with NULL.
• Perform a recursive inorder traversal.
• If prev is NULL, update it to current.
• If prev is not NULL, validate if the current node is larger than prev.
• Update the prev to current.

Similarly, the algorithm for the iterative inorder approach follows as

• Maintain a prev node, initialize it with NULL and maintain a stack for inorder traversal.
• Perform an iterative inorder traversal.
• If prev is NULL, update it to current.
• If prev is not NULL, validate if the current node is larger than prev.
• Update the prev to current.

Implementation

The java implementation for the inorder approach to check for bst follows as

Output:

C++ implementation for the inorder approach to check for bst follows as

Output:

Python implementation for the inorder approach to check for bst follows as

Output:

Time Complexity

In the recursive approach, we are visiting each node in the tree and compare it with the previous node. So the time complexity will be O(N). Similarly, in the iterative approach, we are looping over the stack of size N, so the time complexity will be O(N).

Space Complexity

The recursive approach doesn’t require any auxiliary space, but it internally maintains a recursion stack of size H(height of tree) for inorder traversal. So the space complexity will be O(H). The iterative approach uses an auxiliary stack for inorder traversal that at most go to size H(height of tree), so the space complexity will be O(H).