I'm researching binary trees and came across this section describing storage methods.

It states that:

In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child...

...This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time...

Can someone demonstrate or further explain why this happens?


  • $\begingroup$ Do you understand the other method that Wikipedia suggests, namely storing a binary tree as an array? Compare the space usage of both methods. $\endgroup$ – Yuval Filmus Mar 2 '19 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.