Today we are going to learn how to build a binary tree from its linked list representation. First I will describe how a linked list can be used to represent a binary tree, then I will describe a simple algorithm for constructing the binary tree represented by the linked list, and lastly I will share the code implementing the algorithm.
Representing a binary tree with a linked list
A binary tree can be represented by an array as follows: If a parent node is stored in index i, then it’s left and right children are stored at indices 2*i + 1, and 2*i + 2 respectively. However, unlike an array, a linked list typically does not support indexes, this means we cannot rely on indexes to build a binary tree from a linked list.
Suppose that we have a linked list representing a binary tree as shown in Image 1 below, how can we build the binary tree without the ability to use indices?
Image 1
First, let's understand how the linked list represents the binary tree. Looking at Image 2, if we pretended that the list was instead an array with indices, we could determine the left and right children of each node. I went ahead and drew lines from each parent to each of its children. Using this information we could draw the binary tree, which I did below.
Image 2
Look for the patterns
Now that we understand how the binary tree is represented by the linked list, let's see if we can find any patterns.
First, notice how all children sharing the same parent are located next to each other, starting with the children of the root. In Image 3, children sharing the same parent are highlighted in the same color.
Image 3
Second, looking at the linked list in Image 3, notice how the distance between each parent node and its children increases as we traverse the list. Starting at the root, 1, we see its left child is right next to it in the list. For the next node, 2, its left child is separated by one node in the list. Finally, for node 3, its left child is separated by two nodes. This pattern continues, and the number of nodes between any given parent and its left child keeps increasing linearly.
So we have two patterns:
Children sharing the same parent are next to each other in the list.
The left child of a given node is next to it if it is the root. If it is not the root, it is located one or more nodes away, with the distance being larger as you traverse farther down the list.
Finding a solution
With the above knowledge, it looks like we will need a way to keep two references as we traverse the linked list. One for the parent node, and another for the children of the parent node. As we traverse the list, the distance between the parent and child node references should increase. More specifically, the child reference should traverse the list twice as fast as the parent reference.
Image 4 depicts where the parent and child references should be at the start of each iteration. By having the parent and child reference in the correct locations at the start of each iteration, we will have everything we need to build out our binary tree.
Image 4
The Algorithm
Now that we know what the high level algorithm is, it's time to implement it. For this example I used Python.
As you can see from the code above, in part 4, we implement our algorithm. We use a queue to hold references to the parent nodes, and we use a pointer to keep references to the child nodes. The brunt of the work is done in the while loop. Notice how at the start of each iteration we have a reference to the parent node and its left child node. From these two references we are able to build the tree as we iterate.
Also notice how we update the parent and child references as we iterate so the next iteration will have everything it needs.
Conclusion
As you can see, it helps to really understand the problem before looking for a solution. After understanding the problem you can begin looking for patterns. Once you do those steps, figuring out an algorithm should be much easier.