Validate if Tree is BST in DSA C++ - 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.

bool isBSTUtil(Node* node, int min, int max) {
    if (node == nullptr) return true;
    if (node->data <= min || node->data >= max) return false;
    return isBSTUtil(node->left, min, node->data) &&
           isBSTUtil(node->right, node->data, max);
}

bool isBST(Node* root) {
    return isBSTUtil(root, INT_MIN, INT_MAX);
}
    

This code checks if a binary tree is a BST by making sure every node fits the BST rules within a range.

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 exactly once.

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

Pattern observation: The time grows directly in proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the tree grows linearly with the number of nodes.

Common Mistake

[X] Wrong: "Checking if a tree is BST takes more than linear time because of nested checks."

[OK] Correct: Each node is checked once with simple comparisons, so the total work is just one pass through all nodes.

Interview Connect

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

Self-Check

"What if the tree is given as a sorted array and you want to check if it can form a BST? How would the time complexity change?"