How do binary trees use memory to store its data?

Question

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?

• Bart van Ingen Schenau: What language are you coming from? In many languages, lists are stored as nodes that are not contiguous in memory.
• Frank: You do realize, that you can implement a binary tree via an static array if you can make any assumptions about its size and/or allow for resizes ?
• sw123456: This question is more a generic question rather than one relating to a language, however I am from a python background.I was under the impression that (in python) lists were simply static arrays which when data was appended to, a new array would be created (lets say double the size) so there would be more room. I thought that this was how lists in other languages worked - as opposed to 'Linked-Lists' which, as you say, are nodes that are non contiguous.
• sw123456: Thank you Frank. I can see how that works yes. However, with one which we are unaware of the size, how would these be written in memory?
• user23007: Binary trees, like lists and sets, have no prescribed internal data structure (although there are some data structures that are very convenient to use for them). You could implement a binary tree using nodes and links, as with linked lists, or as a heap (static array), or by nesting dictionaries...

Answer 1

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.