grid47 Exploring patterns and algorithms
Oct 28, 2024
6 min read
Solution to LeetCode 98: Validate Binary Search Tree Problem
You are given the root of a binary tree. Your task is to determine whether the tree is a valid binary search tree (BST). A binary search tree is valid if for every node in the tree, the value of all nodes in its left subtree are less than its own value, and the value of all nodes in its right subtree are greater than its own value.
Problem
Approach
Steps
Complexity
Input: The input consists of the root node of a binary tree.
Example: Input: root = [3,2,4,1,5]
Constraints:
• The tree contains between 1 and 10^4 nodes.
• -2^31 <= Node.val <= 2^31 - 1
Output: Return true if the tree is a valid binary search tree, otherwise return false.
Example: Output: true
Constraints:
• The function must return true if the tree is a valid BST, and false otherwise.
Goal: The goal is to verify if the binary tree satisfies the conditions of a binary search tree at every node.
Steps:
• Traverse the tree in an inorder fashion.
• Check if the node values are in strictly increasing order. If any node violates this rule, return false.
• If the traversal completes without issues, return true.
Goal: The problem ensures that the binary tree follows the given constraints, including the value range for each node.
Steps:
• The tree has at least 1 node.
• Each node's value is within the range [-2^31, 2^31 - 1].
Assumptions:
• The tree is valid and can be represented in the form of a binary tree with integer values.
• Input: Input: root = [3,2,4,1,5]
• Explanation: In this case, the tree is a valid binary search tree because the left subtree contains values less than 3, and the right subtree contains values greater than 3, with the same rule applying recursively to all nodes.
• Input: Input: root = [5,1,4,null,null,3,6]
• Explanation: In this case, the tree is not a valid binary search tree because the right child of node 5 is 4, which is less than 5, violating the BST rule.
Approach: We will use an inorder traversal to verify if the binary tree is a valid BST. In an inorder traversal of a BST, the values of nodes should appear in strictly increasing order. By comparing each node with the previously visited node, we can determine if the tree is a valid BST.
Observations:
• If the tree is a valid BST, an inorder traversal should yield a sorted list of node values.
• We will use a stack-based iterative inorder traversal to ensure we efficiently check all nodes of the tree.
Steps:
• Use a stack to simulate the inorder traversal of the tree.
• Traverse the tree while pushing nodes onto the stack.
• Pop nodes from the stack and check if they are in strictly increasing order.
• If any node violates the BST condition, return false. If the traversal completes successfully, return true.
Empty Inputs:
• An empty tree is considered a valid BST, so return true.
Large Inputs:
• For large trees with up to 10^4 nodes, the solution must be efficient and handle the constraints effectively.
Special Values:
• Ensure that nodes with extreme values (-2^31 and 2^31 - 1) are handled correctly.
Constraints:
• Ensure the solution works efficiently within the given constraints.
Start of the function. We're defining a function to check if a binary tree is a valid Binary Search Tree (BST).
2 : Stack Initialization
stack<TreeNode*> stk;
Here we initialize a stack to help with the iterative in-order traversal of the tree.
3 : Variable Initialization
TreeNode* node = root, *prv =NULL;
We initialize two pointers: 'node' to traverse the tree and 'prv' to keep track of the previous node in the in-order traversal.
4 : While Loop
while(!stk.empty() || node) {
We start a while loop that continues as long as there are nodes to process, either in the stack or in the 'node' variable.
5 : If Condition
if(node) {
If the current node is not null, we process it by pushing it onto the stack.
6 : Stack Push
stk.push(node);
We push the current node onto the stack to visit its left subtree next.
7 : Left Traversal
node = node->left;
Move to the left child of the current node to continue the in-order traversal.
8 : Else Condition
} else {
If there are no more left children to visit (i.e., node is null), we process the node at the top of the stack.
9 : Stack Top
node = stk.top();
Retrieve the top node from the stack, which is the next node in the in-order traversal.
10 : Stack Pop
stk.pop();
Pop the node from the stack after processing it.
11 : BST Validation
if(prv !=NULL&& prv -> val >= node->val)
We check if the previous node's value is greater than or equal to the current node's value. If it is, the tree is not a valid BST.
12 : Return False
returnfalse;
If the previous node's value is greater than or equal to the current node's value, return false because the tree violates BST properties.
13 : Update Previous Node
prv = node;
Update the 'prv' pointer to the current node, which will be used for comparison in the next iteration.
14 : Move Right
node = node->right;
Move to the right child of the current node to continue the in-order traversal.
15 : End of While
}
End of the while loop, indicating that all nodes have been processed.
16 : Return True
returntrue;
If no violations were found, return true indicating the tree is a valid BST.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of nodes in the tree, because we visit each node once during the inorder traversal.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) in the worst case when the tree is skewed and all nodes are pushed onto the stack. In the best case, for a balanced tree, the space complexity is O(h), where h is the height of the tree.
