Node having maximum number of nodes less than its value in its subtree | C ++ program for the above approach ; Stores the nodes to be deleted ; Structure of a Tree node ; Function to create a new node ; Function to compare the current node key with keys received from it left & right tree by Post Order traversal ; Base Case ; Find nodes lesser than the current root in the left subtree ; Find nodes lesser than the current root in the right subtree ; Stores all the nodes less than the current node 's ; Add the nodes which are less than current node in left [ ] ; Add the nodes which are less than current node in right [ ] ; Create a combined vector for pass to it 's parent ; Stores key that has maximum nodes ; Return the vector of nodes ; Driver Code ; Given Tree ; Function Call ; Print the node value
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_map < int , bool > mp ; struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } vector < int > findNodes ( Node * root , int & max_v , int & rootIndex ) { if ( ! root ) { return vector < int > { } ; } vector < int > left = findNodes ( root -> left , max_v , rootIndex ) ; vector < int > right = findNodes ( root -> right , max_v , rootIndex ) ; vector < int > combined ; int count = 0 ; for ( int i = 0 ; i < left . size ( ) ; i ++ ) { if ( left [ i ] < root -> key ) { count += 1 ; } combined . push_back ( left [ i ] ) ; } for ( int i = 0 ; i < right . size ( ) ; i ++ ) { if ( right [ i ] < root -> key ) { count += 1 ; } combined . push_back ( right [ i ] ) ; } combined . push_back ( root -> key ) ; if ( count > max_v ) { rootIndex = root -> key ; max_v = count ; } return combined ; } int main ( ) { Node * root = newNode ( 3 ) ; root -> left = newNode ( 4 ) ; root -> right = newNode ( 6 ) ; root -> right -> left = newNode ( 4 ) ; root -> right -> right = newNode ( 5 ) ; root -> left -> left = newNode ( 10 ) ; root -> left -> right = newNode ( 2 ) ; int max_v = 0 ; int rootIndex = -1 ; findNodes ( root , max_v , rootIndex ) ; cout << rootIndex ; }