Link Tree nodes at each level

Question

Given a binary tree, how would you join the nodes at each level, left to right. Say there are 5 nodes at level three, link all of them from left to right.

I don't need anybody to write code for this.. but just an efficient algorithm.

Thanks

Answer 1

Create a vector of linked lists. Do a DFS keeping track of your level, and for each node you find, add it to the linked list of the level. This will run in O(n) which is optimal.

Is this what you want to do?

Answer 2

I agree with Thomas Ahle's answer if you want to make all of the row-lists at the same time. It seems that you are only interested in making the list for a one specific row.

Let's say you have a giant tree, but you only want to link the 5th row. There's clearly no point in accessing any node below the 5th row. So just do an early-terminated DFS. Unfortunately, you still have to run through all of the ancestors of every node in the list.

But here's the good news. If you have a perfect binary tree (where every single node branches exactly twice except for the last row) then the first row will have 1 one, the second 2, the third 4, the fourth 8 and the fifth 16. Thus there are more nodes on the last row (16) than all the previous put together (1 + 2 + 4 + 8 = 15), so searching through all of the ancestors is still just O(n), where n is the number of nodes in the row.

The worst case on the other hand would be to have the fifth row consist of a single node with a full binary tree above it. Then you still have to search through all 15 ancestors just to put that one node on the list.

So while this algorithm is really your only choice without modifying your data structure its efficiency relies entirely on how populated the row is compared to higher rows.

Answer 3

This is not a direct answer to the question and may not be applicable based on your situation. But if you have control over the creation and maintenance of the binary tree, it would probably be more efficient to maintain the links while building/updating the tree.

If you kept both left and right pointers at each level, then it would be "simple" (always easy to say that word when someone else is doing the work) to maintain them. When inserting a new node at a given level, you know its direct siblings from the parent node information. You can adjust the left and right pointers for the three nodes involved (assuming not at the edge of the tree). Likewise, when removing a node, simply update the left and right pointers of the siblings of the node being removed. Change them to point to each other.