Count Pairs Violating BST Property

Sample Example

We will take an example so the problem statement will be clear for you.

Input:

root = [60, 40, 70, 30, 35, 20, 50]

Output:

The number of Pairs violating BST property is 7

Explanation:

(40, 35) ∵35 < 40 So node 35 should be in the left subtree of the root 40.

(60, 20) ∵20 < 60 So node 20 should be in the left subtree of the root 60.

(40, 20) ∵20 < 40 So, node 20 should be in the left subtree of root 60 and to the left of node 40.

(70, 50) ∵50 < 70 So node 50 should be in the left subtree of the root 70.

(60, 50) ∵50 < 60 So node 50 should be in the left subtree of the root 60.

(35, 20) ∵20 < 35 So node 20 should be in the left subtree of root 60 and to the left of node 35.

(30, 20) ∵20< 30 So, node 20 should be in the left subtree of root 60 and to the left of node 30.

BruteForce Approach

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

Algorithm

• Calculate the Inorder traversal of the tree and store it in an array. Inorder traversal is used to arrange the numbers given in the tree in ascending order.
   
• Count the violating steps, i.e. where array[i] > array[j] and i < j.  We can do this by using two loops.
   
• Return the number of violating steps.

Dry Run

• To represent the structure of a binary search tree, we must first define a BSTnode struct. It has two pointers, left and right, to represent the node's left and right children and an integer val to store the node's value.
   
• Construct an Inorder function that traverses the BST in order recursively and produces a vector of integers that represents the traversal.
   
• The Inorder method returns an empty vector if the root node is NULL. Without that, we repeatedly invoke the inorder function on the left subtree and save the outcome in the lefttree vector. We recursively call the inorder function on the right subtree and put the outcome in the righttree vector.
   
• We append the current node's value to the lefttree vector's end to represent the Inorder traverse of the left subtree.
   
• Finally, we add all the right subtree node’s values of the righttree vector to the end of the lefttree vector, representing the Inorder traversal of the whole BST rooted at the current node. The lefttree vector is the Inorder traversal of our BST [30, 40, 35, 60, 20, 70, 50] named arr vector.
   
• The number of BST node pairs that do not comply with the BST property is represented by the counter ans, which we set to 0.
   
• Next, in the Inorder traversal of the BST, we iterate over all possible pairs of nodes using two loops. If the node's value at location i is higher than the node's value at position j for any pair of nodes (i, j). The BST property is broken {arr[i] > arr[j] and i < j}, and the ans counter is increased.
   
• When i is 30, then for all j > i, we get pairs of (i, j) violating BST property {(30,20)}.
   
• When i is 40, then for all j > i, we get pairs of (i, j) violating BST property {(40,35),(40,20)}.
   
• When i is 35, then for all j > i, we get pairs of (i, j) violating BST property {(35,20)}.
   
• When i is 60, then for all j > i, we get pairs of (i, j) violating BST property {(60,20), (60,50)}.
   
• When i is 70, then for all j > i, we get pairs of (i, j) violating BST property {(70, 50)}.
   
• The program's output in this instance is 7, indicating that there are 7 pairs of nodes in the BST that do not adhere to the BST property.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// Define a structure for a node in a binary search tree (BST)
struct BSTnode{
    int val;
    BSTnode *left, *right;
    BSTnode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
// Define a function to perform the inorder traversal of a BST
vector<int> inorder(BSTnode *root){
    // Base case: if the root is NULL, return an empty vector
    if (root == NULL){
        vector<int> temp;
        return temp;
    }
    // Recursively perform the inorder traversal of the left subtree
    vector<int> lefttree = inorder(root->left);
    // Recursively perform the inorder traversal of the right subtree
    vector<int> righttree = inorder(root->right);
    // Combine the inorder traversals of the left and right subtrees with the root value
    lefttree.push_back(root->val);
    for (auto i : righttree){
        lefttree.push_back(i);
    }
    return lefttree;
}
int main(){
    // Create a binary search tree with seven nodes
    BSTnode *root = new BSTnode(60);
    root->left = new BSTnode(40);
    root->right = new BSTnode(70);
    root->left->left = new BSTnode(30);
    root->left->right = new BSTnode(35);
    root->right->left = new BSTnode(20);
    root->right->right = new BSTnode(50);
    // Check if the tree is empty and output 0 pairs if so
    if (root == NULL){
        cout<< "The Number of Pairs violating BST property is" << " "<<0<<endl;
        return 0;
    }
    // Get the inorder traversal of the binary search tree
    vector<int> arr = inorder(root);
    // Count the number of pairs of nodes that violate the BST property
    int ans = 0;
    for (int i = 0; i < arr.size(); i++){
        for (int j = i + 1; j < arr.size(); j++){
            if (arr[i] > arr[j]){
                ans++;
            }
        }
    }
    // Output the number of pairs of nodes that violate the BST property
    cout << "Number of Pairs violating BST property is" <<" "<< ans << endl;
    return 0;
}

Output:

Implementation in Python

# Define a class for a node in a binary search tree (BST)
class BSTNode:
    def __init__(self, data):
        self.val = data
        self.left = None
        self.right = None

# Define a function to perform the inorder traversal of a BST
def inorder(root):
    # Base case: if the root is None, return an empty list
    if root is None:
        return []
    # Recursively perform the inorder traversal of the left subtree
    left_tree = inorder(root.left)
    # Recursively perform the inorder traversal of the right subtree
    right_tree = inorder(root.right)
    # Combine the inorder traversals of the left and right subtrees with the root value
    return left_tree + [root.val] + right_tree

# Create a binary search tree with seven nodes
root = BSTNode(60)
root.left = BSTNode(40)
root.right = BSTNode(70)
root.left.left = BSTNode(30)
root.left.right = BSTNode(35)
root.right.left = BSTNode(20)
root.right.right = BSTNode(50)

# Get the inorder traversal of the binary search tree
arr = inorder(root)

# Count the number of pairs of nodes that violate the BST property
ans = 0
for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        if arr[i] > arr[j]:
            ans += 1

# Output the number of pairs of nodes that violate the BST property
print("Number of Pairs violating BST property is", ans)

Output:

Time Complexity

The time complexity of the code is O(n^2), where n is the number of nodes in BST. This is because we are iterating over all pairs of elements in the Inorder traversal of the tree twice to count the number of pairs that violate the BST property.

Space Complexity

The space complexity of the code is O(n), where n is the number of nodes in the BST. This is because we are using a vector to store the Inorder traversal of the tree. In the worst case, the recursion stack for the inorder function also takes up O(n) space.

Optimised Approach

We can reduce our time from O(n²) to O(n log n), and we can use the merge sort algorithm to sort and find the number of inversion count (which is the number of pairs violating BST property)

Algorithm

• Compute the Inorder traversal of the tree and store it in an array.
   
• Inorder traversal is used to arrange the numbers given in the tree in ascending order.
   
• Count the inversion count. i.e. where array[i] > array[j] and i < j, which can also be called as violating steps.
   
• This is done easily by using the merge sort algorithm.
   
• Return the number of violating steps.

Dry Run

• To represent the structure of a binary search tree, we must first define a BSTnode struct. It has two pointers, left and right, to represent the node's left and right children and an integer val to store the node's value.
   
•  construct an Inorder function that traverses the BST in order recursively and produces a vector of integers that represents the traversal.
   
• The Inorder method returns an empty vector if the root node is NULL. Without that, we repeatedly invoke the inorder function on the left subtree and save the outcome in the lefttree vector. We recursively call the inorder function on the right subtree and put the outcome in the righttree vector.
   
• We append the current node's value to the lefttree vector's end to represent the Inorder traverse of the left subtree.
   
• Finally, we add all the right subtree node’s righttree vector values to the lefttree vector's end, representing the Inorder traversal of the whole BST rooted at the current node. The lefttree vector is the Inorder traversal of our BST [30, 40, 35, 60, 20, 70, 50] named arr vector.
   
• The merge Sort function is then called with the arguments arr, temp, 0, and n - 1, where n is the length of the arr array. Recursively splitting the input array in half and merging the two sorted halves into a single sorted array while keeping track of the number of inversions(pairs violating BST property) is what the merge Sort function does.
   
• To count the number of inversions in an array using merge sort, we need to count the number of pairs of elements that are out of order.
   
• Firstly, we Divide the array into two halves:

30 40 35   |  60 20 70 50
 

• We Recursively sort the left and right halves using merge sort:

30 35 40   |  20 50 60 70
 

• We Count the number of inversions between the two halves(for the first half, we get the number of inversions to be 1 {(40, 35)} and for the second half, we get the number of inversions to be 3 {(60, 20), (60, 50), (70, 50)}). Since both halves are already sorted, we can use a merge step to count the inversions. We start by comparing the left half's first element with the right half's first element. Since 30 < 20, we know all elements to the right of 30 in the left half are greater than 20. Therefore, we have two inversions: (30, 20) and (40, 20). We then compare the next smallest element in the left half (35) with 20 and get one more inversion: (35, 20).
   
• The total number of inversions in the original array equals the sum of the inversions in the left half, the inversions in the right half, and the inversions between the two halves. So the total number of inversions we get is 7, which is 1 from the first half and 3 from the second half. In the merge step, we get 3 more inversions, so in total, there are  7 inversions present in the Binary search tree, which is equivalent to the number of pairs violating BST properties.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Structure for a node in a binary search tree
struct BSTnode {
    int val;
    BSTnode *left, *right;
    BSTnode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

// Function to perform inorder traversal of a binary search tree and return a sorted vector of values
vector<int> inorder(BSTnode *root) {
    // If the root is null, return an empty vector
    if (root == NULL) {
        vector<int> temp;
        return temp;
    }
    // Recursively traverse the left subtree
    vector<int> lefttree = inorder(root->left);
    // Recursively traverse the right subtree
    vector<int> righttree = inorder(root->right);
    // Append the current node's value to the end of the left subtree vector
    lefttree.push_back(root->val);
    // Append the values of the right subtree vector to the end of the left subtree vector
    for (auto i : righttree) {
        lefttree.push_back(i);
    }
    // Return the sorted vector of values
    return lefttree;
}

// Function to merge two sorted halves of an array and count the number of inversions
int merge(int arr[], int temp[], int left, int mid, int right) {
    int inv_count = 0;
    int i = left;
    int j = mid;
    int k = left;
    // Merge the two halves while counting the number of inversions
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count = inv_count + (mid - i);
        }
    }
    // Copy the remaining elements of the left half to the temp array
    while (i <= mid - 1)
        temp[k++] = arr[i++];
    // Copy the remaining elements of the right half to the temp array
    while (j <= right)
        temp[k++] = arr[j++];
    // Copy the sorted temp array back to the original array
    for (i = left; i <= right; i++)
        arr[i] = temp[i];
    // Return the number of inversions
    return inv_count;
}

// Function to recursively divide an array into halves, sort the halves, and merge them while counting the number of inversions
int merge_Sort(int arr[], int temp[], int left, int right) {
    int mid, inv_count = 0;
    // If the array has more than one element, divide it into halves and merge them
    if (right > left) {
        mid = (left + right) / 2;
        // Recursively sort and merge the left half
        inv_count += merge_Sort(arr, temp, left, mid);
        // Recursively sort and merge the right half
        inv_count += merge_Sort(arr, temp, mid + 1, right);
        // Merge the two halves while counting the number of inversions
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    // Return the number of inversions
    return inv_count;
}
int main(){
    BSTnode *root = new BSTnode(60);
    root->left = new BSTnode(40);
    root->right = new BSTnode(70);
    root->left->left = new BSTnode(30);
    root->left->right = new BSTnode(35);
    root->right->left = new BSTnode(20);
    root->right->right = new BSTnode(50);

    if (root == NULL){
        cout << "Number of Pairs violating BST property is"<< " " << 0 << endl;
        return 0;
    }
    vector<int> a = inorder(root);
    int n = a.size();
    int arr[n];
    for (int i = 0; i < n; i++){
        arr[i] = a[i];
    }
    int temp[n];
    cout << "Number of Pairs violating BST property is"<< " " << merge_Sort(arr, temp, 0, n - 1) << endl;
}

Output:

Implementation in Python

# Define a class to represent a node in the BST
class BSTnode:
    def __init__(self, data):
        self.val = data
        self.left = None
        self.right = None

# Traverse the BST in inorder fashion and return the list of nodes visited
def inorder(root):
    if root is None:
        return []
    lefttree = inorder(root.left)
    righttree = inorder(root.right)
    lefttree.append(root.val)
    lefttree.extend(righttree)
    return lefttree

# Count the number of inversions between left and right halves of the array
def merge(arr, temp, left, mid, right):
    inv_count = 0
    i = left
    j = mid
    k = left
    while (i <= mid - 1) and (j <= right):
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
            inv_count += mid - i
        k += 1
    while i <= mid - 1:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1
    for i in range(left, right + 1):
        arr[i] = temp[i]
    return inv_count

# Recursively divide the array into halves and count the number of inversions
def merge_Sort(arr, temp, left, right):
    inv_count = 0
    if right > left:
        mid = (left + right) // 2
        inv_count += merge_Sort(arr, temp, left, mid)
        inv_count += merge_Sort(arr, temp, mid + 1, right)
        inv_count += merge(arr, temp, left, mid + 1, right)
    return inv_count

# Create a sample BST with 7 nodes and find the number of pairs violating the BST property
if __name__ == '__main__':
    root = BSTnode(60)
    root.left = BSTnode(40)
    root.right = BSTnode(70)
    root.left.left = BSTnode(30)
    root.left.right = BSTnode(35)
    root.right.left = BSTnode(20)
    root.right.right = BSTnode(50)
    # If BST is empty, print 0 and exit
    if root is None:
        print("Number of Pairs violating BST property is 0")
    else:
        # Convert inorder traversal of BST into an array
        a = inorder(root)
        n = len(a)
        arr = [0] * n
        for i in range(n):
            arr[i] = a[i]
        temp = [0] * n
        # Count the number of pairs violating BST property using merge sort and print the result
        print("Number of Pairs violating BST property is", merge_Sort(arr, temp, 0, n - 1))

Output:

Time Complexity

O(nlogn), where n is the number of nodes in Binary Search Tree, The BST's inorder traversal requires O(n) time. Then, in O(n) time, the BST's elements are copied to an array. The time complexity of the merge sort function, which counts the number of inversions, is O(nlogn). The array is split in half recursively, and the two halves are combined while the number of inversions is counted. Hence, the code's overall temporal complexity is O(nlogn).

Space Complexity

O(n), where n is the number of nodes in the Binary Search Tree. This is because the temporary array used in merge sort and the array used to store the BST's items have a space complexity of O(n). Moreover, the space complexity of the merge sort's recursion stack is O(logn). However, the space complexity can be reduced to O(n) because the recursion's maximum depth is O(logn).

Frequently Asked Questions

What are the types of traversals in Binary Tree?

There are three types of traversal of a binary tree.

Inorder tree traversal, Preorder tree traversal, and Postorder tree traversal.

What is Inorder Traversal?

Inorder traversal refers to processing the left, 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.

What are the prerequisites for the binary search tree problem?

We must have a detailed understanding of recursion.

What is time complexity?

The time an algorithm or code takes to execute each instruction is known as its time complexity.

What is space complexity?

The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity".

Conclusion

This article discusses Counting pairs violating the Binary Search Tree property. In detail, we have seen the problem statement, sample example, algorithm, dry run, and implementation in two languages. Along with this, we also saw the time and space complexity.

We hope this blog has helped you enhance your knowledge of the count of cycles in a connected undirected graph. If you want to learn more, then check out our articles.

• Merge Sort
• Diameter of binary tree
• Detect cycles in undirected graph
   

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!