TreesLesson 28Free preview

DSA Array Implementation

This lesson is part of DSA · All levels

Summary

Binary trees can be stored in an array by mapping the position of nodes: the left child is at index 2i+1 and the right child at 2i+2 when index is zero-based. This mapping is very efficient for a complete tree because it doesn't require a pointer. But for a rare tree, many slots arrays become empty and waste memory.

Key points

The left hand side at 2i+1 and the right hand side at 2i+2 for the zero-based index
Suitable for complete binary trees like heaps
No pointers needed so it's economical and fast-accessible
Memory is erased when the tree is rare because of the many empty slots

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.