Count pairs violating BST property

Urwashi Priya
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss a binary search tree problem asked frequently in Interviews.

A common prerequisite before any Binary Search Tree problem is the knowledge of recursion because, without understanding recursion, things can become difficult for us to understand. Before we proceed, we must know what a Binary Search Tree(BST) is?

A Binary Search Tree or BST is a binary tree that follows a particular property that any node in the left subtree in the Binary Search Tree is smaller than the root node, and any node in the right subtree in the Binary Search Tree is greater than the root node. Every subtree of the Binary Search Tree must follow this property.

Problem statement

The problem is to Count pairs violating BST property.

We are given a binary tree, and we need to check if there is any pair of the node that violates the property of the binary search tree. If any such node exists, we need to return the count of how many such nodes exists.

Example: Say Binary search tree given is:

 

Pairs violating BST property are: 

(30,25) ∵25<30 So it should be in the left subtree.

(50,10)

(30,10)

(60,40)

(50,40)

(25,15)

(20,10)

So the answer would be 7.

Brute-force Approach

We can approach how to Count pairs violating BST property using the inorder traversal concept.

Compute the inorder traversal of the tree and store it in an array.

Inorder traversal is used because this is used to arrange the numbers given in the tree in ascending order.

Count the violating steps. i.e where array[i]>array[j]

This can be done easily by using two loops.

Return the number of violating steps.

 

Time Complexity = O(n²)

n: no of elements in the binary search tree.

Space complexity: O(n).

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

count_voilating_nodes

If you can’t solve, don’t be sad. This is a part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm()

___________________________________________________________________

procedure pairsViolatingBST(Node *root ):

___________________________________________________________________

1.   Write code for inorder traversal and store it in an array.

2.   if root == NULL: return 0

3.   vector<int>arr = inOrder(root); int ans = 0;

4.   for i = 0 to arr.size()

for j = i + 1 to arr.size()

if arr[i] > arr[j]: ans++

5.   Return ans.

end procedure

___________________________________________________________________

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

//Structure of a binary tree
struct Node {
    int data;
    Node * left, * right;
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

vector < int > inOrder(Node * root) {
    if (root == NULL) {
        vector < int > temp;
        return temp;
    }
    vector < int > a = inOrder(root -> left);
    vector < int > b = inOrder(root -> right);

    a.push_back(root -> data);
    for (int i = 0; i < b.size(); i++) {
        a.push_back(b[i]);
    }
    return a;
}

int pairsViolatingBST(Node * root) {
    if (root == NULL) {
        return 0;
    }
    // Finding the inOrder Traversal for given tree.
    vector < int > arr = inOrder(root);
    int ans = 0;
    // Counting the number of pairs.
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[i] > arr[j]) {
                ans++;
            }
        }
    }
    return ans;
}

int main() {
    Node * root = new Node(50);
    root -> left = new Node(30);
    root -> right = new Node(60);
    root -> left -> left = new Node(20);
    root -> left -> right = new Node(25);
    root -> right -> left = new Node(10);
    root -> right -> right = new Node(40);
    cout << pairsViolatingBST(root);

}

 

Output:

Sample Input: 
50 30 60 20 25 10 40

Sample Output:
7

Complexity Analysis

Time Complexity: O(n²).

Analysing Time Complexity:

Time taken to search violations=

Space complexity: O(n).

Optimised Approach

We can reduce our time from O(n²) to O(n log n) using the inversion count concept. The inversion count uses a merge-sort algorithm to sort and find the number of pairs violating the ascending sequence of numbers.

Compute the inorder traversal of the tree and store it in an array.

Inorder traversal is used because this is used to arrange the numbers given in the tree in ascending order.

Count the violating steps. i.e where array[i]>array[j]

This is done easily by using merge sort or Fenwick tree.

Return the number of violating steps.

 

Time Complexity = O(n * log n)

n: no of elements in the binary search tree.

Space complexity: O(n).

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

problem.

If you can’t solve, don’t be sad. This is a part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm()

___________________________________________________________________

procedure pairsViolatingBST(Node *root ):

___________________________________________________________________

1.   Write code for inorder traversal and store it in an array.

2.   if root == NULL: return 0

3.   vector<int>arr = inOrder(root); int ans = 0;

4.   Code for Fenwick tree. Store in a function and call it.

5.   Return ans.

 

end procedure

___________________________________________________________________

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

//Structure of a binary tree
struct Node {
    int data;
    Node * left, * right;
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

vector < int > inOrder(Node * root) {
    if (root == NULL) {
        vector < int > temp;
        return temp;
    }
    vector < int > a = inOrder(root -> left);
    vector < int > b = inOrder(root -> right);

    a.push_back(root -> data);
    for (int i = 0; i < b.size(); i++) {
        a.push_back(b[i]);
    }
    return a;
}

void update(int index, int x, int n, vector < int > & fenwick) {
    while (index <= n) {
        fenwick[index] += x;
        index += (index & (-index));
    }

}

int query(int n, int index, vector < int > & fenwick) {
    int ans = 0;
    while (index > 0) {
        ans += fenwick[index];
        index -= (index & (-index));
    }
    return ans;
}

int countInversion(vector < int > & arr) {
    // Finding the inversion count using fenwick tree
    int maxn = * max_element(arr.begin(), arr.end());
    vector < int > fenwick(maxn + 5, 0);
    int ans = 0;
    for (int i = 0; i < arr.size(); i++) {
        int temp = query(maxn, arr[i], fenwick);
        // Number of elements greater than arr[i]
        ans += (i - temp);
        // Incresing the count of arr[i]
        update(arr[i], 1, maxn, fenwick);
    }
    return ans;

}
int pairsViolatingBST(Node * root) {
    if (root == NULL) {
        return 0;
    }
    // Finding the inOrder Traversal for given tree.
    vector < int > arr = inOrder(root);
    int ans = countInversion(arr);
    return ans;
}

int main() {
    Node * root = new Node(50);
    root -> left = new Node(30);
    root -> right = new Node(60);
    root -> left -> left = new Node(20);
    root -> left -> right = new Node(25);
    root -> right -> left = new Node(10);
    root -> right -> right = new Node(40);
    cout << pairsViolatingBST(root);

}

 

Output:

Sample Input: 
50 30 60 20 25 10 40
Sample Output:
7

Complexity Analysis

Time Complexity: O(n*log n).

Analysing Time Complexity:

Time taken to search violations=n*log n

Space complexity: O(n).

Frequently Asked Questions

  1. What are the prerequisites for the binary search tree problem?
    Answer) We must have a detailed understanding of recursion.
    To know more about recursion, click here.
     
  2. What are the steps to follow in such kind of question? 
    Answer)step 1: find one or more base cases.
    Step 2: Call the same function for the left subtree.
    Step 3: Call the same function for the right subtree.
    Step 4: Join results and then evaluate what is asked for.
    Follow split and combine approaches.
     
  3. What is inorder traversal?
    Answer) Inorder traversal refers to processing the left subtree, root, and right subtree. The main concept used in this problem is inorder traversal is used for arranging elements of the binary search tree in ascending order.

Key Takeaways

This article taught us how to Count pairs violating BST property. We discussed its implementation using illustrations, pseudocode, and proper code.

We hope you could take away the critical techniques like analysing problems by walking over the execution of the examples and also finding out the recursive pattern followed in the most binary search tree (BST) problems.

Now, we recommend you to practice problem sets based on binary search trees to master your fundamentals. You can get a wide range of questions similar to this on CodeStudio

It's not the end. Must solve the problem of similar types. 

Happy Coding.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think