Sorting a list of numbers by frequencies in Java using a BST tree

This extends Sorting a list of numbers by frequencies in Java using a map to use a BST instead of a Map.

PROBLEM to solve: Sort a list of numbers by frequency of their occurrences. For example

INPUT: [ 5, 3, 7, 7, 7, 5, 4, 8 ]

OUTPUT: [7, 7, 7, 5, 5, 3, 4, 8]

Pre-requisite: Assumes that you understand the basics concepts like recursion, tree traversal algorithms and Basic Java Tree structure interview Q&A with coding.

ALGORITHM to use

1. Create a BST (Binary Search Tree) and while creating BST maintain the frequency of each repeated number.

2. Do an Inorder traversal of BST and flatten every element and frequency of each element in a list.

3. Sort the list by frequency. More frequent to less frequent.

4. Traverse through the sorted by frequency array to repeat the numbers based on the frequency. E.g. if number 7 occurs three times, output 3 times.

Sort-By-Frequency-BST

Define Data and Node (i.e. Tree) classes as shown below

Define “CreateBST” to construct a tree of Nodes from an array and traverse InOrder to flatten to list

Define the executable main class to take input and create output by executing the algorithm defined in order.

Output:


Java & Big Data Interview FAQs

Java Key Areas Interview Q&As

800+ Java Interview Q&As

Java & Big Data Tutorials

Top