Count Pairs Violating BST Property

Problem Overview

In a valid BST the inorder sequence is sorted.

Intuition

In a valid BST the inorder sequence is sorted. A pair violates that property when the node that appears earlier in inorder has the larger value. Those pairs are exactly the inversions of the inorder sequence, so the tree question becomes an inversion count. Merge sort counts them while it sorts: whenever a value from the right half is taken first, it is smaller than every value still waiting in the left half.

Algorithm

1Walk the tree inorder with an explicit stack and store the values in an int array.
2Return 0 when the tree has fewer than two nodes.
3Merge adjacent runs from width 1 upward, writing each merged run into a second buffer.
4When the next right value is smaller, add the number of remaining left values to the inversion total.
5Swap the two buffers after each width and return the total.

Example Walkthrough

Input: inorder sequence 3, 1, 2

1. The pair (3, 1) is out of order, and so is (3, 2).
2. The pair (1, 2) is already in order.
3. Merge sort reports both inversions, so the answer is 2.

Output: 2

Common Pitfalls

• Equal values are not inversions. Take the left value first when the two heads are equal.
• A valid BST has a sorted inorder and therefore zero violating pairs.
• A skewed tree makes a recursive inorder as deep as the node count. An explicit stack keeps that walk on the heap.
• The inversion total can be about n squared over 2, so accumulate it in a 64-bit integer.

Count Pairs Violating BST Property.java

Java

// Approach: Inorder of a BST is sorted, so a violating pair is an inversion in
// that sequence. Write the inorder straight into an int array, then count
// inversions with a bottom-up merge. Each level merges from one buffer into
// the other, so every element is written once per level.
// Complexity: O(n log n) time, O(n) extra space.
import java.util.ArrayDeque;

class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    public int pairsViolatingBST(Node root) {
        int n = count(root);
        if (n < 2)
            return 0;

        int[] a = new int[n];
        fill(root, a);
        int[] b = new int[n];
        long inv = 0;
        for (int width = 1; width < n; width <<= 1) {
            for (int low = 0; low < n; low += width << 1) {
                int mid = Math.min(low + width, n);
                int high = Math.min(low + (width << 1), n);
                if (mid >= high)
                    System.arraycopy(a, low, b, low, high - low);
                else
                    inv += merge(a, b, low, mid, high);
            }
            int[] swap = a;
            a = b;
            b = swap;
        }
        return (int) inv;
    }

    private int count(Node root) {
        int n = 0;
        ArrayDeque<Node> stack = new ArrayDeque<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            n++;
            cur = cur.right;
        }
        return n;
    }

    private void fill(Node root, int[] arr) {
        int k = 0;
        ArrayDeque<Node> stack = new ArrayDeque<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            arr[k++] = cur.data;
            cur = cur.right;
        }
    }

    private long merge(int[] src, int[] dst, int low, int mid, int high) {
        int i = low, j = mid, k = low;
        long inv = 0;
        while (i < mid && j < high) {
            if (src[i] <= src[j])
                dst[k++] = src[i++];
            else {
                inv += mid - i;
                dst[k++] = src[j++];
            }
        }
        while (i < mid)
            dst[k++] = src[i++];
        while (j < high)
            dst[k++] = src[j++];
        return inv;
    }
}

Was this solution helpful?