The same tree represented in two very different ways visualized using 𝗺𝗲𝗺𝗼𝗿𝘆_𝗴𝗿𝗮𝗽𝗵: Binary Trees
🔗 Binary Tree as Nodes:
The tree is built out of multiple node objects. Each node stores its value and two references, one to its left child and one to its right child.
📦 Binary Tree as List:
The tree is stored in a single list or array. Instead of references, indices represent the relationships between nodes. For a node at index, its children can be found using a simple calculation:
- Left child: 2 * index + 1
- Right child: 2 * index + 2
So, when should you use which representation?
The node-based version makes the structure explicit and intuitive. It is great for education: students can clearly see how nodes are connected while practicing classes and references/pointers. It is flexible and works particularly well for irregular or sparse trees. It is the clearest representation when learning how trees work.
The list-based version can be very efficient for (nearly) balanced trees. It does not need to store child references, requires fewer separate memory allocations, and keeps values close together in memory for improved cache performance.
The same abstract data structure, but with very different trade-offs in clarity, flexibility, and performance.
Which representation would you use?