Editing Binary tree (section)

=== Arrays ===

Binary trees can also be stored in breadth-first order as an [[implicit data structure]] in [[array data structure|arrays]], and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index ''i'', its children are found at indices <math>2i + 1</math> (for the left child) and <math>2i +2</math> (for the right), while its parent (if any) is found at index ''<math>\left \lfloor \frac{i-1}{2} \right \rfloor</math>'' (assuming the root has index zero). Alternatively, with a 1-indexed array, the implementation is simplified with children found at <math>2i</math> and <math>2i+1</math>, and parent found at <math>\lfloor i/2 \rfloor</math>.<ref>{{Cite book| title=Introduction to algorithms| date=2001|publisher=MIT Press|others=Cormen, Thomas H., Cormen, Thomas H.|isbn=0-262-03293-7|edition=2nd|location=Cambridge, Mass.| pages=128| oclc=46792720}}</ref>

This method benefits from more compact storage and better [[locality of reference]], particularly during a preorder traversal. It is often used for [[binary heap]]s.<ref>{{Cite web |last=Laakso |first=Mikko |title=Priority Queue and Binary Heap |url=http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html |access-date=2023-10-11 |website=University of Aalto}}</ref>

[[Image:Binary tree in array.svg|upright=1.2|center|A small complete binary tree stored in an array]]