Katkat
Back

Count invalid nodes in a BST

ApplovinSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of binary search tree invariants and the ability to identify nodes that violate ancestor-imposed value ranges, testing competency with tree data structures and constraint propagation in the coding & algorithms domain.

You are given the root of a binary tree. A valid Binary Search Tree (BST) must satisfy: for every node with value v, all values in its left subtree are strictly < v, and all values in its right subtree are strictly > v (i.e., the constraint is with respect to all ancestors, not just the parent).

Instead of returning a boolean, return the number of nodes that violate the BST rule.

Input

  • The root of a binary tree.
  • Node values are integers.

Output

  • An integer: the count of nodes that are part of at least one BST-order violation (i.e., nodes whose value is not within the valid (low, high) range implied by ancestors).

Notes / Clarifications

  • Use strict inequality (no duplicates allowed in a valid BST).
  • Counting is per node: if a node violates constraints from multiple ancestors, it is still counted once.

Constraints (typical interview assumptions)

  • Number of nodes n up to ~10^5.
  • Aim for O(n) time.