Validate if Tree is BST in DSA Typescript - 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 as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isBST(node: TreeNode | null, min: number = -Infinity, max: number = Infinity): boolean {
  if (node === null) return true;
  if (node.val <= min || node.val >= max) return false;
  return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
}
    

This code checks if a binary tree is a BST by making sure each node's value fits between allowed minimum and maximum 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 tree grows, the function visits every node once to check its value.

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

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The function only checks some nodes, so it runs faster than O(n)."

[OK] Correct: The function must visit every node to be sure the whole tree follows BST rules, so it always checks all nodes.

Interview Connect

Understanding this helps you explain how to verify tree properties efficiently, a common skill in coding interviews.

Self-Check

"What if we used an in-order traversal to check the BST property instead? How would the time complexity change?"