So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists make use of static arrays and when data is appended to the list, if there is no room, a new static array is created elsewhere in memory larger in size so more data can be stored. My question is, how do binary trees use memory to store data? Is each node a memory location which points to two other memory locations elsewhere…not necessarily contiguous locations? Or are they stored in contiguous blocks of memory too like a static array or dynamic list?
Binary Trees: How Memory is Used to Store Data
binary tree
Best Answer
Implementations differ, but traditionally nodes were allocated as needed and as such were generally thought of as non-contiguous. In practice, if the binary tree were being constructed from a data set (e.g., data read from a file), then the node allocations would usually wind up being contiguous, since they were typically allocated sequentially and not interleaved with other allocations. However, if the tree was built dynamically and node creation was interspersed with other memory-allocating operations, then the nodes were non-contiguous. Note that, depending on the heap management scheme used, even "contiguous" node allocations typically had their size rounded up to the heap block size, so one node wouldn't start exactly where the previous node ended.