Skip to content
Advertisement

How do I sort a Binary Search Tree from greatest to least?

I need to return an array of nodes sorted from high to low. At the moment I am trying to implement an inorder traversal which gives me the exact opposite of what I’m looking for.

The tree looks like:

                 10. Captain Picard
                 /                  
          6. Commander Riker       11. Commander Data
            /                        
    4. Lt. Cmdr.   7. Lt. Cmdr.     12. Lt. Cmdr.
        Worf           LaForge           Crusher
                                        
        5. Lieutenant                  13. Lieutenant
        security-officer                    Selar

My function looks like:

listOfficersByExperience(officerNames = []) {
    if (this.leftReport) {
      officerNames = this.leftReport.listOfficersByExperience(officerNames);
    }

    officerNames.push(this.officerName);

    if (this.rightReport) {
      officerNames = this.rightReport.listOfficersByExperience(officerNames);
    }

    return officerNames;
}

From this, I receive:

[
  'Lt. Cmdr. Worf',
  'Lieutenant Security-Officer',
  'Commander Riker',
  'Lt. Cmdr. LaForge',
  'Captain Picard',
  'Commander Data',
  'Lt. Cmdr. Crusher',
  'Lieutenant Selar'
]

When I need to receive:

[
  'Lieutenant Selar',
  'Lt. Cmdr. Crusher',
  'Commander Data',
  'Captain Picard',
  'Lt. Cmdr. LaForge',
  'Commander Riker',
  'Lieutenant Security-Officer',
  'Lt. Cmdr. Worf'
]

Is there a way that I can reverse these nodes or is there a different sorting method that I need/should implement?

Advertisement

Answer

You should just swap the two if statements where you make a recursive call, so that you first visit rightReport and then later leftReport.

listOfficersByExperience(officerNames = []) {
    if (this.rightReport) {
      officerNames = this.rightReport.listOfficersByExperience(officerNames);
    }

    officerNames.push(this.officerName);

    if (this.leftReport) {
      officerNames = this.leftReport.listOfficersByExperience(officerNames);
    }

    return officerNames;
}
User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement