Algo question: Tree data structures while drawn as Nodes with children, are usually better implemented with (resizable) arrays?

Better than adjacency matrices? Using resizable arrays is more space efficient, especially with trees (O(n^2) vs O(n)) but if you want to check if two nodes are neighbors (or parent-child in case of trees), then you can do it in O(1) using adjacency matrix, but with resizable arrays the worst case is O(n).

You can store the node as an object and have the pointer to the parent node and a resizable array of children in its properties, then the parent-child relationship can be checked in O(1) while the space still being O(n). But if the tree is weighted then there might be a few use cases where adjacency matrices are preferable.

@rithvikp I think tree need not have a adjacency matrix. Graphs only need em. Binary trees are better implemented as arrays , interms of time complexity. If the '-ary ness' is fixed then children can be accessed in one shot.

@rithvikp wow sounds like you really know your algos. Now I'm worried...

Not really sure about adjacency arrays but now reading up it seems trees aren't really implemented as linked nodes. It's just easier to visualize it that way.

@xaero how do you attach the new node to the correct parent node?

@billgates I am about to graduate from college and I am on a job hunt, that's why I remember all these. If you spend a couple of weeks doing only algos, you will too 🙂

@xaero You are assuming it's a binary search tree, right?

@xaero That will definitely work. But i recently learnt that it is very inefficient in time, because each time you create a node, you have to either invoke malloc/calloc , and that is kinda inefficient if you do it over and over again. If you allocate expandable arrays with spare space and always expand the array by a fixed multiple of the earlier capacity, it can be proven that memory allocation is kinda O(1).

@xaero but then how do you keep it balanced. Usually you can't go up from a child, only down? But it's the parent that has to do the balancing?

I don't really remember the specifics but with an array you can go both ways I think just cause you can calculate the index... Though not quite sure how to balance that either...

@xaero I have zero experience with java. So maybe..

@xaero For balancing you can use AVL trees ( which is not that complicated anyway )

I’ve almost never actually used a linked list in practice. Certainly not in the past 20 years. Arrays are just simpler, more efficient and support random access. Linked lists allow for constant-time insertion, but *only* if you already have the nodes you want to insert between. Otherwise you have to search for them, which means an O(n) iteration for a linked list.

Also there’s no point in using a linked list or an array for a binary tree since each node of the tree always has at most two branches. Just use left/right pointers.

@devios1 but then what do you use to store a BST?

@billgates Objects with two nullable pointers/references (one per branch).

@devios1 that would be considered a linked list though? Instead of one child the more has 2

How do you add or remove a child in the correct spot? You're have to keep track of all the leaf nodes and which is still empty?

@billgates No a linked list is a linear chain of references, where each node points to the next node in the list, and optionally also back to the previous (in doubly-linked).

A binary tree on the other hand has two possible directions to go at each node, left and right, as well as optionally back up to the parent.

@billgates To insert a new node N in a binary tree you would take its target parent node P with existing left and right pointers, and if you wanted to insert N on its right side, you would set N.right = P.right and then P.right = N.

You're right that implementationally a binary tree is very similar to a linked list, except it has two forward directions instead of one.

On the other hand if you imagine a non-binary tree where each node can have an arbitrary number of children, that's when you could use either a linked list or an array to store the children.

I would almost always choose an array.

@devios1 but you would first need to find the target for each insert? Or you just remember the last node that was inserted, then bubble it up from there? Or bubbly down from root? I guess Maybe it's similar

@billgates Yes you need to have a pointer to the node you want to insert it under. How you keep track of nodes depends on your use case, but in the worst case you would have to search for it first.

@billgates Trees are very general-purpose data structures, just like lists/arrays so there are many possible uses for them. Maintaining a sorted list of things (what it sounds like you're doing) is only one such possibility. File system hierarchies are also trees, but in that case you rarely traverse the tree because everything is done local to a particular directory.

Or another way you could think of that is the user does the traversing themselves.

Don't mind me, I'm just bored and wanted to talk about data structures.

@devios1 regarding linked list - they are faster to add, because when you add the element, you *know* where to add. If you by to add at the end - is just a matter of keeping the pointer to the list item.
Regarding arrays - they are costly in terms of resize and even more costly when it comes to inserting elements in the middle. You can use Vector or Areaylists and preallocate them with more elements, but it still costs more.
So in general - you should use linked lists when capacity is variable, insertion time (insertion, not replacement, at random place) is important. Arrays are better when capacity is known. Also, arrays are supposed to be better when it comes to memory layout, they can fit into the same memory page while linked lists probably won't.

@mt3o The biggest benefit of arrays is that they are random access. If you know the index you want you can read it in O(1). Accessing the nth element of a linked list on the other hand is O(n). Linked lists do offer constant-time inserts, but like I said earlier, you still have to have a pointer to the nodes you want to insert between. Inserting onto the end of an array with available capacity is a constant time operation, but anywhere else is not.

But I disagree that you would use linked lists when you need a dynamically-sized array. Most implementations of vectors use arrays under the hood, I would expect primarily because of random access.

@devios1 :)
Vector keeps some data blocks reserved for future use, that solves some problems, but:
1) as you add more items, it eventually has to reallocate the data into new memory block
2) arrays require tons of work when you have to reorder the data, not just access it. Examples:
+ get last item from the array and insert it in the beginning
+ maintain a order of elements
+ balance the tree
In those cases, linked-list-like structures are more performant.

Also, you focus on random access for the list/array. That's rarely the case. LIFO and FIFO are main two applications of lists and they don't require random access.
Ordered set requires scanning the collection disregarding which structure is used below.
Arrays (C-like) are nice for data structures that have constant size. If you dynamically allocate stored objects and keep only pointers, you loose the benefit of fitting the data in CPU cache.

Going on, if you want to add/remove elements that can't be indexed with int-keys, you go into direction of HashMaps. And they use c-like arrays (or vectors) for the buckets and store buckets as linked lists :)

All those circumstances led creators of PHP to conclusion that arrays should be implemented as black-red trees, allocated in non-continuous memory block. :) which resembles linked lists :)

@devios1 Linked list is more of a linking mechanism. So it need not be linear to be a linked list. If you store a pointer to store the address of the next node.. that is a LINKED LIST. Doesnt matter you store multiple of them.

@aEEEdev That’s not true. I’m not sure what gave you that idea. Lists are a linear data structure. A tree is not a list. Look up the definition of “list”.

@devios1 Okay sorry lists are linear. But the idea in a tree is kind of maintaining two seperate lists ( not exactly ), one for right one for left etc.. Although the definition is recursive in a tree, which makes it non linear. I was trying to stress 'Linked' part of a linked list, whereas i should have called it a linked structure.

@aEEEdev Right, the linking mechanism is the same in both. You could say a tree node is linked to its child nodes in the same way a list node is linked to its next node.