Editing Binary search tree (section)

==Examples of applications==
===Sort===
{{Main article|Tree sort}}
Binary search trees are used in sorting algorithms such as [[tree sort]], where all the elements are inserted at once and the tree is traversed at an in-order fashion.<ref>{{cite web|url=https://www.cs.princeton.edu/courses/archive/spring19/cos226/lectures/study/32BinarySearchTrees.html|publisher=[[Princeton University School of Engineering and Applied Science]]|first=Arvind|last=Narayanan|access-date=21 October 2021|title=COS226: Binary search trees|archive-url=https://web.archive.org/web/20210322040843/https://www.cs.princeton.edu/courses/archive/spring19/cos226/lectures/study/32BinarySearchTrees.html|archive-date=22 March 2021|url-status=live|year=2019|via=cs.princeton.edu}}</ref> BSTs are also used in [[quicksort]].<ref>{{cite web|url=http://mathcenter.oxford.emory.edu/site/cs171/bstQuicksortConnection/|title=A Connection Between Binary Search Trees and Quicksort|archive-url=https://web.archive.org/web/20210226103159/http://mathcenter.oxford.emory.edu/site/cs171/bstQuicksortConnection/|publisher=[[Oxford College of Emory University]], The Department of Mathematics and Computer Science|first=Li|last=Xiong|url-status=live|access-date=4 June 2022|archive-date=26 February 2021}}</ref>

===Priority queue operations===
{{main|Priority queue}}
Binary search trees are used in implementing [[priority queue]]s, using the node's key as priorities. Adding new elements to the queue follows the regular BST insertion operation but the removal operation depends on the type of priority queue:<ref>{{cite web|publisher=[[Cornell University]], [[Cornell University College of Engineering|Department of Computer Science]]|first=Andrew|last=Myers|title=CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps|url=https://www.cs.cornell.edu/courses/cs4120/2016sp/lectures/lec_heaps/|archive-date=21 October 2021|url-status=live|archive-url=https://web.archive.org/web/20211021202727/https://www.cs.cornell.edu/courses/cs4120/2016sp/lectures/lec_heaps/|access-date=21 October 2021}}
</ref>
* If it is an ascending order priority queue, removal of an element with the lowest priority is done through leftward traversal of the BST.
* If it is a descending order priority queue, removal of an element with the highest priority is done through rightward traversal of the BST.