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

The question is: how does the time needed grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func isBST(node *TreeNode, min, max *int) bool {
    if node == nil {
        return true
    }
    if (min != nil && node.Val <= *min) || (max != nil && 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 verifying each node's value is within allowed min and max limits recursively.

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 (n times for n nodes).

How Execution Grows With Input

As the tree grows, the function visits each node once, so the work grows directly with the number of nodes.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to check the tree grows in direct proportion to the number of nodes.

Common Mistake

[X] Wrong: "The check is faster because it stops early if a node fails, so it's less than O(n)."

[OK] Correct: While it may stop early sometimes, in the worst case it must check every node, so the time complexity is still O(n).

Interview Connect

Understanding this time complexity helps you explain how efficient your tree checks are and shows you can reason about recursive algorithms clearly.

Self-Check

"What if we changed the code to use an in-order traversal and check if values are sorted? How would the time complexity change?"