Find the maximum count of duplicate nodes in a Binary Search Tree

Optimized Approach

Find the maximum count of duplicate nodes in a binary search tree to solve this problem. We need to find the inorder traversal of the bst because it will give us the nodes of the tree in sorted order, so the idea to solve this problem is simple we will do recursive inorder traversal, and we will keep track of the previous node value, and if the previous node value is equal to the current node value then we will increase the count, and if the count is greater than maximum count then we will replace maximum count with the current count. 

Algorithm

1. We will make a function inorder() which will take one argument, i.e., the tree's root. We will also maintain four variables, two for counting duplicates, one for storing the answer value, and the last one for storing the previous node.
2. We will do recursive inorder traversal, keeping track of the previous node. If the value of the previous node is equal to the current node's value, then we will increase the count. If the count value becomes greater than the maximum count value, we will replace the maximum value and simultaneously assign the answer with the root node's value.
3. We will now call this function in main, and after that, we will print the answer variable.

Code in C++

// C++ implementation to find the maximum count of duplicate nodes in a binary search tree
#include <bits/stdc++.h>
using namespace std;

// Structure of each node of BST
struct Node
{
    int key;
    struct Node *left, *right;
};

// Function to create a new BST node
Node *TreeNode(int data)
{
    Node *temp = new Node();
    temp->key = data;
    temp->left = temp->right = NULL;
    return temp;
}

// Function to insert node in bst
struct Node *insert(struct Node *node, int key)
{
    // If the tree is empty, then return a new node
    if (node == NULL)
        return TreeNode(key);

    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    // Return the (unchanged) node pointer
    return node;
}

// max_count to store the value of maximum count till now
// count_for_duplicates to store current count value
// and answer to store the node having maximum duplicates
int max_count = 0, count_for_duplicates = 1, answer;

struct Node *previous = NULL;

// Function to find the maximum count of duplicate nodes in a binary search tree
void inorder(struct Node *root)
{
    // base case
    if (!root)
    {
        return;
    }
    inorder(root->left);
    if (previous != NULL)
    {
       // if previous value is equal to root value
        // then increase variable count_for_duplicates
        if (previous->key == root->key)
        {
            count_for_duplicates++;
        }
        // else reset its value to one
        else
        {
            count_for_duplicates = 1;
        }
    }
    // if the variable count_for_duplicates has more value than
    // the maximum count value then replace the maximum count value
    // and assign answer the current node's value
    if (count_for_duplicates > max_count)
    {
        max_count = count_for_duplicates;
        answer = root->key;
    }
    // assign previous the value of current node
    previous = root;
    inorder(root->right);
}
int main()
{

   /* Formation of BST 
            5
            / \
          3   7
          /\   /\
        3  3 6  8
    */

    struct Node *root = NULL;
    root1 = insert(root, 5);
    insert(root, 3);
    insert(root, 3);
    insert(root, 3);
    insert(root, 7);
    insert(root, 6);
    insert(root, 8);

    inorder(root);

    cout << "The node with a maximum count of duplicates is: " << answer << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

The node with a maximum count of duplicates is: 3 

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time Complexity: O(N)

Since we are doing inorder traversal of the bst and inorder traversal can be done in O(N), the time complexity is O(N).

Space Complexity: O(1)

If we ignore the stack space occupied by the recursive calls, the space complexity will be O(1).

Frequently asked questions

Q1. What is a binary tree?

Ans. A binary tree is a data structure in programming languages to represent the hierarchy.  Each node of the binary tree can have either 0,1, or 2 children.

Q2. What are leave nodes in a tree?

Ans. Leave nodes of a tree are those nodes that don’t have any children, and both the pointers of the nodes point to null.

Q3. What is a binary search tree?

Ans. A binary search tree is a sorted binary tree in which all the nodes of the binary tree have a value greater than their left child node and a value smaller than their right child node.

Key takeaways

In this article, we discussed the problem find the maximum count of duplicate nodes in a binary search tree, and we have discussed its most efficient approach. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

Check out this problem - Diameter Of Binary Tree

You can learn more about binary search trees here. Until then, Keep Learning and Keep Coding and practicing on Code studio.