Coding Interview Questions | Validate Binary Search Tree (BST)

January 19th, 2024

Validate BST Problem Introduction:

This summary will talk about my solution to the validate BST problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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.

How do you solve the Validate BST Problem using a Stack?

Solution:

function isValidBST(root: TreeNode | null): boolean {
  if (!root) {
    return true;
  }

  const nodeStack = [
    {
      node: root,
      lower: Number.NEGATIVE_INFINITY,
      upper: Number.POSITIVE_INFINITY,
    },
  ];

  while (nodeStack.length > 0) {
    const { node, lower, upper } = nodeStack.pop()!;

    // Check if the current node's value is within the valid range
    if (node.val <= lower || node.val >= upper) {
      return false;
    }

    // Push left child with updated upper bound
    if (node.left) {
      nodeStack.push({ node: node.left, lower, upper: node.val });
    }

    // Push right child with updated lower bound
    if (node.right) {
      nodeStack.push({ node: node.right, lower: node.val, upper });
    }
  }

  return true;
}

Valid Binary Search Tree Solution Summary:

Below is a breakdown of the key aspects of the solution above for determining if a binary tree is a valid binary search tree (BST):

1. Base Case Handling: The algorithm first checks if the root is null, returning true as a valid BST in this case.

2. Stack-based Iterative Approach: The solution employs a stack-based iterative approach to traverse the binary tree while keeping track of the valid range for each node.

3. Node and Bounds Tracking: The algorithm utilizes a stack (nodeStack) to keep track of nodes to be explored. For each node, it also maintains the lower and upper bounds representing the valid range of values for that node.

4. Range Checking: We check if the current node’s value is within the valid range defined by the lower and upper bounds. If not, it returns false, indicating an invalid BST.

5. Updating Bounds for Children: The algorithm updates the bounds for the left and right children of each node during traversal. The left child’s upper bound is set to the current node’s value, and the right child’s lower bound is set similarly.

6. Final Result: The function returns true if the traversal completes without encountering any invalid values, indicating that the binary tree is a valid BST.

Complexities

1. Time Complexity: The time complexity of the solution is determined by the number of nodes in the binary tree, denoted as O(n), where n is the number of nodes.

2. Space Complexity: The space complexity is O(n), where n is the number of nodes in the binary tree. The space required by the stack is directly proportional to the number of nodes, as each node is pushed onto the stack during traversal.