Validate if Tree is BST in DSA Javascript - Time & Space Complexity

Time Complexity: Validate if Tree is BST

O(n)

Understanding Time Complexity

We want to know how long it takes to check if a tree follows the rules of a Binary Search Tree (BST).

How does the time needed grow when the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.value <= min || node.value >= max) return false;
  return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}
    

This code checks if a binary tree is a BST by making sure every node's value fits between allowed min and max limits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

As the number of nodes grows, the function visits each node one time.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The time grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows in a straight line with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Checking only the immediate children is enough to confirm a BST."

[OK] Correct: Because a node deeper in the tree might break the BST rule, so we must check all nodes with proper min and max limits.

Interview Connect

Understanding this helps you show how to carefully check all parts of a tree, a skill useful in many tree problems.

Self-Check

"What if we remove the min and max limits and only compare a node with its immediate children? How would the time complexity and correctness change?"