 # Validate Binary Search Tree

Given the `root` of a binary tree, determine if it is a valid binary search tree (BST).

valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

## Problem Statement

The problem is to determine if a binary tree is a valid binary search tree (BST). A valid BST is defined as a binary tree where the left subtree of a node contains only nodes with keys less than the node's key, the right subtree of a node contains only nodes with keys greater than the node's key, and both the left and right subtrees must also be binary search trees. The goal is to design an algorithm to check whether the given binary tree is a valid BST or not.

## Examples ```Input: root = [2,1,3]
Output: true``` ```Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.```

## Clarifying Questions

1. Can you define what you mean by a binary tree?
2. Can you define what you mean by a binary search tree (BST)?
3. Are there any size constraints on the binary tree?
4. Can we assume that the keys in the binary tree are unique?
5. Are there any performance requirements for the solution?
6. Is the binary tree guaranteed to be balanced or can it be unbalanced?
7. Can we use additional data structures or algorithms to solve this problem?
8. Can we assume that the input tree is a proper binary tree, with each node having at most two children?
9. Are there any constraints on the range of values that can be stored in the binary tree?

## Solutions

There are several approaches to solving the problem of determining whether a binary tree is a valid binary search tree (BST). Here are some of the most common ones:

### Recursive Inorder Traversal:

Traverse the BST using an inorder traversal and store the previous node visited. For each node, check if its value is greater than the previous node's value. This approach requires O(n) time and O(h) space complexity, where n is the number of nodes in the tree and h is the height of the tree.

#### Algorithm:

a. Traverse the left subtree recursively.

b. Check if the current node's value is greater than the value of the previously visited node (initially set to negative infinity).

c. If the current node's value is not greater than the previously visited node's value, return False.

d. Traverse the right subtree recursively.

e. If all nodes are visited and the function has not yet returned False, return True.

Time complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space complexity: O(h), where h is the height of the binary tree. This is because we use the call stack to maintain the state of the recursive calls. In the worst case, when the binary tree is skewed, the height can be O(n), which makes the space complexity O(n).

### Iterative Inorder Traversal:

Traverse the BST using an iterative inorder traversal and store the previous node visited. For each node, check if its value is greater than the previous node's value. This approach requires O(n) time and O(h) space complexity, where n is the number of nodes in the tree and h is the height of the tree.

#### Algorithm:

a. Initialize a stack to store the nodes to be visited and a variable to store the previous node's value (initially set to negative infinity).

b. Traverse the BST using an iterative inorder traversal.

c. For each node visited, if its value is not greater than the previous node's value, return False.

d. Push the node's right child onto the stack, if it exists.

e. Set the previous node's value to the current node's value.

f. If all nodes are visited and the function has not yet returned False, return True.

Time complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space complexity: O(h), where h is the height of the binary tree. This is because we use the stack to maintain the state of the iterative calls. In the worst case, when the binary tree is skewed, the height can be O(n), which makes the space complexity O(n).

### Recursive approach with Range:

Check if each node in the BST is within a certain range of values, defined by the maximum and minimum values that the node's value can take. This approach requires O(n) time and O(h) space complexity, where n is the number of nodes in the tree and h is the height of the tree.

#### Algorithm:

a. Traverse the BST recursively.

b. For each node, check if its value is within a certain range defined by the maximum and minimum values of its parent node. The root node can have an infinite range.

c. If the node's value is not within the range, return False.

d. Traverse the left and right subtrees recursively with an updated range.

e. If all nodes are visited and the function has not yet returned False, return True.

Time complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space complexity: O(n), where n is the number of nodes in the binary tree. This is because we use the call stack to maintain the state of the recursive calls. In the worst case, when the binary tree is skewed, the space complexity can be O(n).

### Depth-First Search (DFS):

Traverse the BST using a depth-first search approach, and keep track of the range of valid values for each node in the tree. This approach requires O(n) time and O(h) space complexity, where n is the number of nodes in the tree and h is the height of the tree.

#### Algorithm:

a. Traverse the BST recursively.

b. For each node, check if its value is within a certain range defined by the minimum and maximum values of its parent node.

c. If the node's value is not within the range, return False.

d. Recursively traverse the left and right subtrees with an updated range.

e. If all nodes are visited and the function has not yet returned False, return True.

a. Traverse the BST recursively.

b. For each node, check if its value is within a certain range defined by the minimum and maximum values of its parent node.

c. If the node's value is not within the range, return False.

d. Recursively traverse the left and right subtrees with an updated range.

e. If all nodes are visited and the function has not yet returned False, return True.

Time complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space complexity: O(h), where h is the height of the binary tree. This is because we use a stack to maintain the state of the DFS. In the worst case, when the binary tree is skewed, the height can be O(n), which makes the space complexity O(n).

Traverse the BST using a breadth-first search approach, and check if each node's value is greater than the minimum value of its right subtree and less than the maximum value of its left subtree. This approach requires O(n) time and O(n) space complexity, where n is the number of nodes in the tree.

#### Algorithm:

a. Initialize a queue to store the nodes to be visited and an array to store the minimum and maximum values for each node visited.

b. Enqueue the root node onto the queue with a range of negative infinity to positive infinity.

c. While the queue is not empty, dequeue a node and its range from the queue.

d. Check if the node's value is within its range.

e. If the node's value is not within its range, return False.

f. Enqueue the left and right children of the node with updated ranges onto the queue.

g. If all nodes are visited and the function has not yet returned False, return True.

Time complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space complexity: O(n), where n is the number of nodes in the binary tree. This is because we use a queue to maintain the state of the BFS. In the worst case, when all nodes are at the same level, the maximum number of nodes in the queue can be n.

All the approaches have the same time complexity of O(n) since they all visit each node exactly once. However, the space complexity varies among the approaches.

The most optimal approach in terms of space complexity is the Recursive Inorder Traversal and Iterative Inorder Traversal approaches, as they both have a space complexity of O(h) where h is the height of the binary tree. This is because they do not store all nodes at once, but only maintain the state of the traversal.

The Recursive and Iterative approaches both have the same space complexity, but the Iterative approach is preferred in some cases because it does not rely on the call stack and can therefore handle larger trees without causing a stack overflow.

In summary, the Iterative Inorder Traversal approach is the most optimal in terms of both time and space complexity for determining if a binary tree is a valid BST.

Share: 