Medium

Validate Binary Search Tree

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

A 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

Can you define what you mean by a binary tree?
Can you define what you mean by a binary search tree (BST)?
Are there any size constraints on the binary tree?
Can we assume that the keys in the binary tree are unique?
Are there any performance requirements for the solution?
Is the binary tree guaranteed to be balanced or can it be unbalanced?
Can we use additional data structures or algorithms to solve this problem?
Can we assume that the input tree is a proper binary tree, with each node having at most two children?
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.

      
     
        // Definition for a binary tree node.
        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
        
        public class Solution {
            // Define a variable to store the previously visited node's value.
            private int prevVal = int.MinValue;
            
            public bool IsValidBST(TreeNode root) {
                // If the root is null, return true.
                if (root == null) {
                    return true;
                }
                
                // Recursively traverse the left subtree.
                if (!IsValidBST(root.left)) {
                    return false;
                }
                
                // Check if the current node's value is greater than the previously visited node's value.
                if (root.val <= prevVal) {
                    return false;
                }
                
                // Update the previously visited node's value to the current node's value.
                prevVal = root.val;
                
                // Recursively traverse the right subtree.
                return IsValidBST(root.right);
            }
        }

      
     
        class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
            
    class Solution:
        def __init__(self):
            # Define a variable to store the previously visited node's value.
            self.prevVal = float('-inf')
            
        def isValidBST(self, root: TreeNode) -> bool:
            # If the root is null, return true.
            if not root:
                return True
            
            # Recursively traverse the left subtree.
            if not self.isValidBST(root.left):
                return False
            
            # Check if the current node's value is greater than the previously visited node's value.
            if root.val <= self.prevVal:
                return False
            
            # Update the previously visited node's value to the current node's value.
            self.prevVal = root.val
            
            # Recursively traverse the right subtree.
            return self.isValidBST(root.right)

      
     
        class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            
            public TreeNode(int val, TreeNode left, TreeNode right) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
            
            public TreeNode(int val) {
                this.val = val;
                this.left = null;
                this.right = null;
            }
        }
        
        class Solution {
            // Define a variable to store the previously visited node's value.
            private int prevVal = Integer.MIN_VALUE;
            
            public boolean isValidBST(TreeNode root) {
                // If the root is null, return true.
                if (root == null) {
                    return true;
                }
                
                // Recursively traverse the left subtree.
                if (!isValidBST(root.left)) {
                    return false;
                }
                
                // Check if the current node's value is greater than the previously visited node's value.
                if (root.val <= prevVal) {
                    return false;
                }
                
                // Update the previously visited node's value to the current node's value.
                prevVal = root.val;
                
                // Recursively traverse the right subtree.
                return isValidBST(root.right);
            }
        }

      
      
 

            // Definition for a binary tree node.
            struct TreeNode {
                int val;
                TreeNode* left;
                TreeNode* right;
                
                TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr) {
                    this->val = val;
                    this->left = left;
                    this->right = right;
                }
            };
            
            class Solution {
                // Define a variable to store the previously visited node's value.
                int prevVal = INT_MIN;
                
            public:
                bool isValidBST(TreeNode* root) {
                    // If the root is null, return true.
                    if (root == nullptr) {
                        return true;
                    }
                    
                    // Recursively traverse the left subtree.
                    if (!isValidBST(root->left)) {
                        return false;
                    }
                    
                    // Check if the current node's value is greater than the previously visited node's value.
                    if (root->val <= prevVal) {
                        return false;
                    }
                    
                    // Update the previously visited node's value to the current node's value.
                    prevVal = root->val;
                    
                    // Recursively traverse the right subtree.
                    return isValidBST(root->right);
                }
            };

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.

      
     
        // Definition for a binary tree node.
        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
        
        public class Solution {
            public bool IsValidBST(TreeNode root) {
                // Define a stack to store the nodes in the traversal.
                Stack<TreeNode> stack = new Stack<TreeNode>();
                
                // Define a variable to store the previously visited node's value.
                int prevVal = int.MinValue;
                
                // Traverse the tree using an iterative inorder traversal.
                while (stack.Count > 0 || root != null) {
                    // Traverse the left subtree until the leftmost node is reached.
                    while (root != null) {
                        stack.Push(root);
                        root = root.left;
                    }
                    
                    // Pop the top node from the stack and check if its value is greater than the previously visited node's value.
                    root = stack.Pop();
                    if (root.val <= prevVal) {
                        return false;
                    }
                    
                    // Update the previously visited node's value to the current node's value.
                    prevVal = root.val;
                    
                    // Traverse the right subtree.
                    root = root.right;
                }
                
                // If all checks pass and all nodes are visited, the tree is a valid BST.
                return true;
            }
        }

      
     
        # Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def isValidBST(self, root: TreeNode) -> bool:
# Define a stack to store the nodes in the traversal.
stack = []

# Define a variable to store the previously visited node's value.
prevVal = float('-inf')

# Traverse the tree using an iterative inorder traversal.
while stack or root:
# Traverse the left subtree until the leftmost node is reached.
while root:
    stack.append(root)
    root = root.left

# Pop the top node from the stack and check if its value is greater than the previously visited node's value.
root = stack.pop()
if root.val <= prevVal:
    return False

# Update the previously visited node's value to the current node's value.
prevVal = root.val

# Traverse the right subtree.
root = root.right

# If all checks pass and all nodes are visited, the tree is a valid BST.
return True

      
        class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            
            public TreeNode(int val, TreeNode left, TreeNode right) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
            
            public TreeNode(int val) {
                this.val = val;
                this.left = null;
                this.right = null;
            }
        }
        
        class Solution {
            
            public boolean isValidBST(TreeNode root) {
                // Define a stack to store the nodes in the traversal.
                Stack<TreeNode> stack = new Stack<>();
                    // Define a variable to store the previously visited node's value.
                    int prevVal = Integer.MIN_VALUE;
                    
                    // Traverse the tree using an iterative inorder traversal.
                    while (!stack.isEmpty() || root != null) {
                        // Traverse the left subtree until the leftmost node is reached.
                        while (root != null) {
                            stack.push(root);
                            root = root.left;
                        }
                        
                        // Pop the top node from the stack and check if its value is greater than the previously visited node's value.
                        root = stack.pop();
                        if (root.val <= prevVal) {
                            return false;
                        }
                        
                        // Update the previously visited node's value to the current node's value.
                        prevVal = root.val;
                        
                        // Traverse the right subtree.
                        root = root.right;
                    }
                    
                    // If all checks pass and all nodes are visited, the tree is a valid BST.
                    return true;
            }
        }

      
 
    class Solution {
        public:
        bool isValidBST(TreeNode* root) {
            // Define a stack to store the nodes in the traversal.
            vector<TreeNode*> stack;
            // Define a variable to store the previously visited node's value.
            int prevVal = INT_MIN;
            
            // Traverse the tree using an iterative inorder traversal.
            while (!stack.empty() || root != nullptr) {
                // Traverse the left subtree until the leftmost node is reached.
                while (root != nullptr) {
                    stack.push(root);
                    root = root->left;
                }
                
                // Pop the top node from the stack and check if its value is greater than the previously visited node's value.
                root = stack.top();
                stack.pop();
                if (root->val <= prevVal) {
                    return false;
                }
                
                // Update the previously visited node's value to the current node's value.
                prevVal = root->val;
                
                // Traverse the right subtree.
                root = root->right;
            }
            
            // If all checks pass and all nodes are visited, the tree is a valid BST.
            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.

      
        // Definition for a binary tree node.
        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
        
        public class Solution {
            public bool IsValidBST(TreeNode root) {
                // Call the helper function to perform the recursive traversal and check if the tree is a valid BST.
                return IsValidBSTHelper(root, long.MinValue, long.MaxValue);
            }
            
            private bool IsValidBSTHelper(TreeNode node, long minVal, long maxVal) {
                // If the node is null, it is a valid BST.
                if (node == null) {
                    return true;
                }
                
                // Check if the current node's value is within the valid range.
                if (node.val <= minVal || node.val >= maxVal) {
                    return false;
                }
                
                // Recursively check if the left and right subtrees are valid BSTs.
                return IsValidBSTHelper(node.left, minVal, node.val) && IsValidBSTHelper(node.right, node.val, maxVal);
            }
        }

      
     
        class TreeNode:
            def init(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
        
        class Solution:
            def isValidBST(self, root: TreeNode) -> bool:
                # Call the helper function to perform the recursive traversal and check if the tree is a valid BST.
                return self.isValidBSTHelper(root, float('-inf'), float('inf'))
            def isValidBSTHelper(self, node: TreeNode, minVal: float, maxVal: float) -> bool:
                # If the node is null, it is a valid BST.
                if not node:
                    return True
                
                # Check if the current node's value is within the valid range.
                if node.val <= minVal or node.val >= maxVal:
                    return False
                
                # Recursively check if the left and right subtrees are valid BSTs.
                return self.isValidBSTHelper(node.left, minVal, node.val) and self.isValidBSTHelper(node.right, node.val, maxVal)

      
        public class Solution {
            public boolean isValidBST(TreeNode root) {
            // Call the helper function to perform the recursive traversal and check if the tree is a valid BST.
            return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
            }
            private boolean isValidBSTHelper(TreeNode node, long minVal, long maxVal) {
                // If the node is null, it is a valid BST.
                if (node == null) {
                    return true;
                }
                
                // Check if the current node's value is within the valid range.
                if (node.val <= minVal || node.val >= maxVal) {
                    return false;
                }
                
                // Recursively check if the left and right subtrees are valid BSTs.
                return isValidBSTHelper(node.left, minVal, node.val) && isValidBSTHelper(node.right, node.val, maxVal);
            }

        }

      
  
            // Definition for a binary tree node.
            class TreeNode {
            public:
                int val;
                TreeNode* left;
                TreeNode* right;
            
                TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr) {
                    this->val = val;
                    this->left = left;
                    this->right = right;
                }
            };
            
            class Solution {
            public:
                bool isValidBST(TreeNode* root) {
                    // Call the helper function to perform the recursive traversal and check if the tree is a valid BST.
                    return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
                }
            
            private:
                bool isValidBSTHelper(TreeNode* node, long minVal, long maxVal) {
                    // If the node is null, it is a valid BST.
                    if (node == nullptr) {
                        return true;
                    }
            
                    // Check if the current node's value is within the valid range.
                    if (node->val <= minVal || node->val >= maxVal) {
                        return false;
                    }
            
                    // Recursively check if the left and right subtrees are valid BSTs.
                    return isValidBSTHelper(node->left, minVal, node->val) && isValidBSTHelper(node->right, node->val, maxVal);
                }
            };

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.

      
        // Definition for a binary tree node.
        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
        
        public class Solution {
            public bool IsValidBST(TreeNode root) {
                // If the root is null, it is a valid BST.
                if (root == null) {
                    return true;
                }
                
                // Initialize the stack with the root node and its lower and upper bounds.
                Stack<(TreeNode node, long lowerBound, long upperBound)> stack = new Stack<(TreeNode node, long lowerBound, long upperBound)>();
                stack.Push((root, long.MinValue, long.MaxValue));
                
                // Process nodes in the stack until it is empty.
                while (stack.Count > 0) {
                    // Pop the next node and its lower and upper bounds.
                    (TreeNode node, long lowerBound, long upperBound) = stack.Pop();
                    
                    // Check if the current node's value is within the valid range.
                    if (node.val <= lowerBound || node.val >= upperBound) {
                        return false;
                    }
                    
                    // Push the right child with its lower and upper bounds.
                    if (node.right != null) {
                        stack.Push((node.right, node.val, upperBound));
                    }
                    
                    // Push the left child with its lower and upper bounds.
                    if (node.left != null) {
                        stack.Push((node.left, lowerBound, node.val));
                    }
                }
                
                // All nodes have been visited and the tree is a valid BST.
                return true;
            }
        }

      
     
        class Solution:
            def isValidBST(self, root: TreeNode) -> bool:
                # If the root is None, it is a valid BST.
                if root is None:
                return True
                # Initialize the stack with the root node and its lower and upper bounds.
                stack = [(root, float('-inf'), float('inf'))]
                
                # Process nodes in the stack until it is empty.
                while stack:
                    # Pop the next node and its lower and upper bounds.
                    node, lowerBound, upperBound = stack.pop()
                    
                    # Check if the current node's value is within the valid range.
                    if node.val <= lowerBound or node.val >= upperBound:
                        return False
                    
                    # Push the right child with its lower and upper bounds.
                    if node.right:
                        stack.append((node.right, node.val, upperBound))
                    
                    # Push the left child with its lower and upper bounds.
                    if node.left:
                        stack.append((node.left, lowerBound, node.val))
                
                # All nodes have been visited and the tree is a valid BST.
                return True

      
        public class Solution {
            public boolean isValidBST(TreeNode root) {
            // If the root is null, it is a valid BST.
            if (root == null) {
            return true;
            }
            // Initialize the stack with the root node and its lower and upper bounds.
            Stack<Tuple<TreeNode, Long, Long>> stack = new Stack<>();
            stack.push(new Tuple<TreeNode, Long, Long>(root, Long.MIN_VALUE, Long.MAX_VALUE));
            
            // Process nodes in the stack until it is empty.
            while (!stack.isEmpty()) {
                // Pop the next node and its lower and upper bounds.
                Tuple<TreeNode, Long, Long> tuple = stack.pop();
                TreeNode node = tuple.getItem1();
                Long lowerBound = tuple.getItem2();
                Long upperBound = tuple.getItem3();
                
                // Check if the current node's value is within the valid range.
                if (node.val <= lowerBound || node.val >= upperBound) {
                    return false;
                }
                
                // Push the right child with its lower and upper bounds.
                if (node.right != null) {
                    stack.push(new Tuple<TreeNode, Long, Long>(node.right, node.val, upperBound));
                }
                
                // Push the left child with its lower and upper bounds.
                if (node.left != null) {
                    stack.push(new Tuple<TreeNode, Long, Long>(node.left, lowerBound, node.val));
                }
            }
            
            // All nodes have been visited and the tree is a valid BST.
            return true;
        }

    }

      
  
           
            
        class Solution {
            public:
            bool isValidBST(TreeNode* root) {
            // If the root is null, it is a valid BST.
            if (root == nullptr) {
            return true;
            }
            // Initialize the stack with the root node and its lower and upper bounds.
            stack<pair<TreeNode*, long>> s;
            s.push({root, LONG_MIN});
            s.push({root, LONG_MAX});
            
            // Process nodes in the stack until it is empty.
            while (!s.empty()) {
                // Pop the next node and its lower and upper bounds.
                auto [node, lowerBound] = s.top();
                s.pop();
                auto [node2, upperBound] = s.top();
                s.pop();
                
                // Check if the current node's value is within the valid range.
                if (node->val <= lowerBound || node->val >= upperBound) {
                    return false;
                }
                
                // Push the right child with its lower and upper bounds.
                if (node->right != nullptr) {
                    s.push({node->right, node->val});
                    s.push({node->right, upperBound});
                }
                
                // Push the left child with its lower and upper bounds.
                if (node->left != nullptr) {
                    s.push({node->left, lowerBound});
                    s.push({node->left, node->val});
                }
            }
            
            // All nodes have been visited and the tree is a valid BST.
            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).

Breadth-First Search (BFS):

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.

      
     
        // Definition for a binary tree node.
        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
        
        public class Solution {
            public bool IsValidBST(TreeNode root) {
                // If the root is null, it is a valid BST.
                if (root == null) {
                    return true;
                }
                
                // Create a queue for BFS.
                Queue<TreeNode> queue = new Queue<TreeNode>();
                
                // Create a queue for storing the lower and upper bounds for each node.
                Queue<(TreeNode node, long lowerBound, long upperBound)> boundsQueue = new Queue<(TreeNode node, long lowerBound, long upperBound)>();
                
                // Initialize the queue with the root node and its lower and upper bounds.
                queue.Enqueue(root);
                boundsQueue.Enqueue((root, long.MinValue, long.MaxValue));
                
                // Process nodes in the queue until it is empty.
                while (queue.Count > 0) {
                    // Dequeue the next node and its lower and upper bounds.
                    TreeNode node = queue.Dequeue();
                    (TreeNode parentNode, long lowerBound, long upperBound) = boundsQueue.Dequeue();
                    
                    // Check if the current node's value is within the valid range.
                    if (node.val <= lowerBound || node.val >= upperBound) {
                        return false;
                    }
                    
                    // Enqueue the left child with its lower and upper bounds.
                    if (node.left != null) {
                        queue.Enqueue(node.left);
                        boundsQueue.Enqueue((node, lowerBound, node.val));
                    }
                    
                    // Enqueue the right child with its lower and upper bounds.
                    if (node.right != null) {
                        queue.Enqueue(node.right);
                        boundsQueue.Enqueue((node, node.val, upperBound));
                    }
                }
                
                // All nodes have been visited and the tree is a valid BST.
                return true;
            }
        }

      
     
        class Solution:
            def isValidBST(self, root: TreeNode) -> bool:
                # If the root is null, it is a valid BST.
                if not root:
                return True
                # Create a queue for BFS.
                queue = []

                # Create a queue for storing the lower and upper bounds for each node.
                bounds_queue = []

                # Initialize the queue with the root node and its lower and upper bounds.
                queue.append(root)
                bounds_queue.append((root, float('-inf'), float('inf')))

                # Process nodes in the queue until it is empty.
                while queue:
                    # Dequeue the next node and its lower and upper bounds.
                    node = queue.pop(0)
                    parent_node, lower_bound, upper_bound = bounds_queue.pop(0)
                    
                    # Check if the current node's value is within the valid range.
                    if node.val <= lower_bound or node.val >= upper_bound:
                        return False
                    
                    # Enqueue the left child with its lower and upper bounds.
                    if node.left:
                        queue.append(node.left)
                        bounds_queue.append((node, lower_bound, node.val))
                    
                    # Enqueue the right child with its lower and upper bounds.
                    if node.right:
                        queue.append(node.right)
                        bounds_queue.append((node, node.val, upper_bound))

                # All nodes have been visited and the tree is a valid BST.
                return True

      
     
        class Solution {
            public boolean isValidBST(TreeNode root) {
            // If the root is null, it is a valid BST.
            if (root == null) {
            return true;
            }
            // Create a queue for BFS.
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            
            // Create a queue for storing the lower and upper bounds for each node.
            Queue<Triple<TreeNode, Long, Long>> boundsQueue = new LinkedList<Triple<TreeNode, Long, Long>>();
         
            // Initialize the queue with the root node and its lower and upper bounds.
            queue.offer(root);
            boundsQueue.offer(new Triple<>(root, Long.MIN_VALUE, Long.MAX_VALUE));
            
            // Process nodes in the queue until it is empty.
            while (!queue.isEmpty()) {
                // Dequeue the next node and its lower and upper bounds.
                TreeNode node = queue.poll();
                Triple<TreeNode, Long, Long> bounds = boundsQueue.poll();
                
                // Check if the current node's value is within the valid range.
                if (node.val <= bounds.getLeft() || node.val >= bounds.getRight()) {
                    return false;
                }
                
                // Enqueue the left child with its lower and upper bounds.
                if (node.left != null) {
                    queue.offer(node.left);
                    boundsQueue.offer(new Triple<>(node, bounds.getLeft(), node.val));
                }
                
                // Enqueue the right child with its lower and upper bounds.
                if (node.right != null) {
                    queue.offer(node.right);
                    boundsQueue.offer(new Triple<>(node, node.val, bounds.getRight()));
                }
            }
            
            // All nodes have been visited and the tree is a valid BST.
            return true;
        }

    }

      
      
        class Solution {
            public:
            bool isValidBST(TreeNode* root) {
            // If the root is null, it is a valid BST.
            if (root == nullptr) {
            return true;
            }
            // Create a queue for BFS.
            queue<TreeNode*> queue;
            
            // Create a queue for storing the lower and upper bounds for each node.
            queue<pair<TreeNode*, long long>> boundsQueue;
            
            // Initialize the queue with the root node and its lower and upper bounds.
            queue.push(root);
            boundsQueue.push({root, LLONG_MIN, LLONG_MAX});
            
            // Process nodes in the queue until it is empty.
            while (!queue.empty()) {
                // Dequeue the next node and its lower and upper bounds.
                TreeNode* node = queue.front();
                queue.pop();
                auto [parentNode, lowerBound, upperBound] = boundsQueue.front();
                boundsQueue.pop();
                
                // Check if the current node's value is within the valid range.
                if (node->val <= lowerBound || node->val >= upperBound) {
                    return false;
                }
                
                // Enqueue the left child with its lower and upper bounds.
                if (node->left != nullptr) {
                    queue.push(node->left);
                    boundsQueue.push({node, lowerBound, node->val});
                }
                
                // Enqueue the right child with its lower and upper bounds.
                if (node->right != nullptr) {
                    queue.push(node->right);
                    boundsQueue.push({node, node->val, upperBound});
                }
            }
            
            // All nodes have been visited and the tree is a valid BST.
            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.

Updated: Nov 21, 2023

« Subarray Sum Equals K

String Compression »