SimuVedaAlgorithms Lab Open in the lab

Trees / Intermediate

Validate a Binary Search Tree Visualizer

Each node gets a range (low, high). The root may be anything. Going left, the node’s value becomes the new high; going right, it becomes the new low. A value outside its range breaks the tree.

Start the Validate a Binary Search Tree simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. 55 was hung as the right child of 40. It is bigger than its parent, so a parent-only check would accept it.
  2. 50 must be between −∞ and ∞.
  3. 50 fits. Its left side must be below 50, its right side above it.
  4. 30 must be between −∞ and 50.
  5. 30 fits. Its left side must be below 30, its right side above it.
  6. 20 must be between −∞ and 30.
  7. 20 fits. Its left side must be below 20, its right side above it.
  8. 40 must be between 30 and 50.
  9. 40 fits. Its left side must be below 40, its right side above it.
  10. 55 must be between 40 and 50.
  11. 55 is not smaller than 50. The tree is not a valid BST.
  12. Invalid: 55 is on the wrong side of an ancestor.

Try it with your own input →

Validate a binary search tree in Java, Python, C++, C and JavaScript

boolean isValid(TreeNode node, long low, long high) {
  if (node == null) return true;
  if (node.val <= low || node.val >= high) return false;
  return isValid(node.left, low, node.val)
      && isValid(node.right, node.val, high);
}
// call: isValid(root, Long.MIN_VALUE, Long.MAX_VALUE)
def is_valid(node, low, high):
    if node is None:
        return True
    if node.val <= low or node.val >= high:
        return False
    return (is_valid(node.left, low, node.val)
            and is_valid(node.right, node.val, high))

# call: is_valid(root, float('-inf'), float('inf'))
bool isValid(TreeNode* node, long long low, long long high) {
  if (!node) return true;
  if (node->val <= low || node->val >= high) return false;
  return isValid(node->left, low, node->val)
      && isValid(node->right, node->val, high);
}
// call: isValid(root, LLONG_MIN, LLONG_MAX)
#include <limits.h>

int isValid(struct TreeNode* node, long long low, long long high) {
  if (node == NULL) return 1;
  if (node->val <= low || node->val >= high) return 0;
  return isValid(node->left, low, node->val)
      && isValid(node->right, node->val, high);
}
// call: isValid(root, LLONG_MIN, LLONG_MAX)
function isValid(node, low, high) {
  if (node === null) return true;
  if (node.val <= low || node.val >= high) return false;
  return isValid(node.left, low, node.val)
      && isValid(node.right, node.val, high);
}
// call: isValid(root, -Infinity, Infinity)

In an interview

LeetCode 98, Validate Binary Search Tree: is every node bigger than everything on its left and smaller than everything on its right?

Checking only node.left < node < node.right is the classic wrong answer: the extra value here passes that check and still breaks the tree. An inorder walk that must be strictly increasing is the other correct method.

More trees