I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree.
At the time, I thought “This will be easy, I’ll just Google for an algorithm to determine the X,Y position of each node, then do something to draw each node on the screen”.
But it turns out Googling for a simple and easytofollow algorithm for drawing nice trees is very hard.
My initial Google attempts lead me to the ReingoldTilford Algorithm.
This sounded exactly like what I wanted, however I was having a lot of trouble in understanding the algorithm so I could convert it into my language of choice (C#). Every article I found seemed to be written for a much smarter person than myself, and I had some difficulty following what they were doing and converting the logic to C#.
After much time spent going through research papers and browsing sample code, I think I finally understand it. So here’s my attempt at explaining the algorithm for drawing trees in an aesthetically pleasing way, using simple terms.
The Example
I’m going to use the example tree from a 1991 journal article by Dr. Dobbs. I found this article the easiest to understand and work my way through, and it would probably be worthwhile to read it if you’re looking into drawing nice trees for yourself. It also contains some more details about what is considered an “aesthetically pleasing tree”, which I won’t talk about in detail because its easy to find online if needed.
The sample tree from the article that I will be using looks like this:
Introduction to The Algorithm
Determining the Y position of each node is easy, so I’m not going to go into detail about it here. The main trouble is determining an appropriate X position for each node.
Here is a very brief overview of the logic I used to determine an appropriate X position of each node. You could probably just take this and figure out how to get the X,Y values yourself in whatever language you want, or I’ll go into each step in more detail later.
 Do a postorder traversal of the tree
 Assign an X value to each node of 0 if it’s a leftmost node, or leftSibling.X + 1 if it’s not.

For each parent node, we want the node centered over the children. This would be the midway point between the first child’s X position, and the last child’s X position.
If the parent has no left sibling, change it’s X value to this midpoint value. If it has a left sibling, we’re going to store it in another node property. I’m calling this property Mod just because that’s what I see it called in other examples.
The Mod property is used to determine how much to modify the children’s X values in order to center them under the parent node, and will be used when we’re done with all our calculates to determine the final X value of each node. It should actually be set to Parent.X – MiddleOfChildrenX to determine the correct amount to shift the children by.
 Check that this tree does not conflict with any of the previous sibling trees, and adjust the Mod property if needed. This means looping through each Y level in the current node, and checking that the rightmost X value of any sibling to the left of the node does not cross the leftmost X value of any child in the current node.
 Do a second walk through the tree to determine that no children will be drawn offscreen, and adjust the Mod property if needed. This can happen when if the Mod property is negative.
 Do a third walk through the tree to determine the final X values for each node. This will be the X of the node, plus the sum of all the Mod values of all parent nodes to that node.
Now lets go through each step in more detail.
First Traversal of Tree
We’re going to do a preorder traversal of the tree for the first walk through, meaning we draw the tree from the bottom up, going from left to right. See the initial drawing of the tree? The nodes have letters on them, A through O. This is the order which the postorder traversal will process the nodes.
This iteration of the tree can be broken up into 3 steps:
 Assign an X value to each node of
leftSibling.X + 1
, or0
if no leftSibling  Move child nodes under parent node
 Verify no children conflict with other trees
Assigning initial X values
The first step is to calculate a “local X” value value for each node. This is the X value within that set of children only.
So the X value of each node after this step would look like this:
The code I use for this is as follows
private void CalculateInitialX(TreeNode node) { foreach (var child in node.Children) CalculateInitialX(child); // if there is a previous sibling in this set, // set X to prevous sibling + designated distance if (!node.IsLeftMost()) node.X = node.GetPreviousSibling().X + 1; else // if this is the first node in a set, set X to 0 node.X = 0; }
Of course, if we actually drew all the nodes at those X values, they would overlap and you wouldn’t be able to see the tree hierarchy.
So we the next step positions the child nodes under their parent.
The Mod Property
Before continuing, I should explain the “Mod” property.
The rest of these steps can involve shifting a Node and all its children over, sometimes multiple times. To do this, we would normally have to loop through all nodes in that subtree and increase their X values, however this can be bad for performance, especially for larger trees.
So to avoid that, we are using the Mod property to tell the node how far it needs to shift all its children by, and then at the end of this this we will do a second walk through the tree to determine the ultimate X position of the node.
To shift a node and all it’s children over during this iteration, increase both it’s X and Mod properties by however much you want.
Positioning Child Nodes under Parents
The next step is to center the child nodes under the parent node. This is actually pretty easy.
First, find the X value that would center a node over it’s children.
 If there is 1 child, the desired X value is the same as the child’s X value.
 If there is more than one child, get the first child’s X and the last child’s X, and find the midway point between the two.
Next, check to see if this is the parent node has any siblings to the left of it. I do this by checking the node’s parent to see if this node is equal to the first node in the parent’s children.
 If this is the first node in the parent’s children, set the X value equal to the desired X value to center the parent over the children.
 If not, assign the Mod value of the node to
node.X  desiredX
to shift children under the parent.
After the third tree traversal is done to calculate the final X values of nodes, this will correctly position the children underneath their parent node.
However it doesn’t stop the trees from overlapping each other. See nodes B, C, H, and I in our tree now?
Checking for node Conflicts
Once you’ve come this far, this step isn’t as bad as it sounds.
The basic logic is if a node has any children, we need to loop through all levels of children and ensure that none of the X values assigned to that child conflict with any X values assigned to previously positioned children at the same level.
To do this, we loop through all children of the current node, and for each Y value we record the minimum X position. Then for each sibling to the left of this node, we loop through all its children and record the maximum X position at each Y. Google told me there’s a fancy term for this: the tree Contour.
So at the time that node N (Blue) is being processed, its Left Contour is { 1.5, 1, 0.0 }
, while the Right Contour of node E (green) is { 0.5, 1.0, 1.5 }
.
Keep in mind that this check uses the final X of the Node as its been calculated so far, and not the local X that we assigned to it initially.
We can see that both the first and second levels overlap, so we need to shift node N over far enough that its Left Contour no longer conflicts with node E’s Right Contour.
In this case, the largest overlapping distance between the two contours is 1.5, and we want to add an extra 1 to make sure the nodes aren’t drawn on top of each other, so we shift node N over by 2.5 places.
Fixing middle trees after resolving a conflict
The previous step fixed the issue of having overlapping nodes, however the end result leaves a lot of empty whitespace in the middle of the tree. Note the position of node F in the tree now:
We shifted node N because it conflicted with E, and now we need to take that distance and apply it evenly across all sibling nodes that are between the two conflicting nodes.
To do that, we divide the distance shifted by the number of nodes between our two conflicting nodes + 1, and shift each of the middle nodes over by this value.
In our case we shifted the node by 2.5, and there is only 1 node (F) between nodes E and N, so we need to shift F over by 2.5 / (1 + 1)
, which results in 1.25
.
And then to be sure we didn’t cause conflicts by shifting the middle nodes, we need to check for conflicts once again.
The end result is the trees will be slightly larger than absolutely necessary, however they will be generated nicely with no conflicting nodes or uneven amounts of whitespace anywhere.
Second Traversal of Tree
Some nodes can have a negative Mod value, which can position the final X of child nodes at a negative value too, and render them off screen.
For an example, if I shift node N to be positioned under A instead of O, I get this result because node H has an X value of 1:
We could check the Mod value at the time it’s calculated to ensure it’s not a negative, however that would only shift our current node over, could resulting in some undesired extra whitespace between sibling nodes.
For example, take a look at the space between nodes G and M in this tree
The best way to fix this problem is to shift the Root Node over enough so that none of the final X values will be negative.
To do this we can get the Right Contour of the Root Node, find the smallest X value, and if its negative we shift the Root Node over by that amount. Remember, to shift a subtree we adjust both the X value and the Mod value by whatever amount we’re shifting by.
Here’s how my code for this looks
private void CheckAllChildrenOnScreen(TreeNode rootNode) { var nodeContour = new Dictionary<int, float>(); GetLeftContour(rootNode, 0, ref nodeContour); float shiftAmount = 0; foreach (var y in nodeContour.Keys) { if (nodeContour[y] + shiftAmount < 0) shiftAmount = (nodeContour[y] * 1); } if (shiftAmount > 0) { rootNode.X += shiftAmount; rootNode.Mod += shiftAmount; } } private void GetLeftContour(TreeNode node, float modSum, ref Dictionary<int, float> values) { if (!values.ContainsKey(node.Y)) values.Add(node.Y, node.X + modSum); else values[node.Y] = Math.Min(values[node.Y], node.X + modSum); modSum += node.Mod; foreach (var child in node.Children) { GetLeftContour(child, modSum, ref values); } }
Here’s how the tree looks now after being shifted over to fit all nodes on the screen:
Third and Final Traversal
The third tree traversal calculates the final X position of each node by adding the Mod value of all its parent nodes to its X value.
I use a simple recursive function for this
private void CalculateFinalX(TreeNode node, float modSum) { node.X += modSum; modSum += node.Mod; foreach (var child in node.Children) CalculateFinalPositions(child, modSum); }
Here’s an image of how the final tree’s X values look
(I have decimal numbers in there because I was by positing nodes 1 space apart to make the math easier to follow, and determining the midpoint often resulted in a decimal)
Final Results
Now all that’s left to do is take this tree of objects with X,Y coordinates, and draw it somewhere!
Final Thoughts
This algorithm is not perfect. I have tested what I could, but I’m sure there’s still bugs in it (I found one while writing this post!). But now I understand how it is supposed to work, and can debug/fix the issues that come up as needed.
The sample code I was using for this project can be downloaded here.
It may not be optimized since it was done for demonstration purposes only, and could be missing some things. It should be thoroughly tested before being used in any kind of production environment.
Many thanks for this article! I don’t think I would have figured this out from original sources like the Dr. Dobb’s article.
In case anyone wants to see a JavaScript version of the algorithm, I did my best to translate it here:
https://github.com/zchtodd/recurser/blob/master/static/recurser.js
There’s a bunch of other stuff in there that’s specific to the project, but the tree algorithm is all in that one file. It seems to be working in general, at least with my use cases.
hi Rachel , I have tried your code to convert into javascript language. but i am not getting the properties of this.parent.children. I mean properties of children for this. parent.children is not defined. It only defined in my second level of tree that is level 1.
Hi Rachel,
I know this is a bit old, but in the text you say checking for conflict is (explicitly) done with the final X values (and you also put that after) but in the source you put the checks at the end of the initial values (before calculating the final ones)
This seems a bit off…
Is that intentional? Am I missing something?
Maybe I just got confused since you’re jumping between traversals a bit 🙂
(Or did you just mean the theoretical check in the text has been done with the final values?)
Sorry… but thanks for breaking down the algorithm and explaining your steps so nicely.
Thanks Rachel, it helped me a lot! One question : what if I don’t have the same width for my nodes ? Any idea on where in the code I should take this into account?
I would probably code it the same way, and just do the calculations in the UI to figure out the appropriate width for each items. The node X,Y should just be a flat number of where in the hierarchy it is, it doesn’t have to be associated with item width. It’s been a while since I looked at the code, but i seem to recall hardcoding a static variable for ITEM_WIDTH in the UI rendering. Maybe look for that? 🙂
Hi Rachel. You really saved my day! 🙂 – This code simplifies a task i have, creating a Decision Tree, so much! 🙂 Thank you very much!
Hi Rachel,
I’m not sure I’m getting the correct results. Part of the challenge is that I might be seeing things wrong. So may I ask for a clarification of definitions?
*** if there is a previous sibling in this set, set X to previous sibling + designated distance
Is a previous sibling a node in the same tree or across all trees? For example are A, D, G, M all siblings, i.e., all nodes on same level?
IsLeftMost() means that we should be finding node “A” ?
IsRightMost() means that we should be finding node “M” ?
Ref: var nodeContour = new Dictionary();
Ref: var siblingContour = new Dictionary();
I am assuming that ‘contours’ contain values for each level that the nodes are on. OK. I’m haven a bit of a challenge in trying to translate this for loop into my language. My For loops work like:
For(index; 1; increment this many times) <index is the value after being incremented.
Could you please explain this for loop?
for (int level = node.Y + 1; level <= Math.Min(siblingContour.Keys.Max(), nodeContour.Keys.Max()); level++)
Appears to be looping for the level below but this next one appears to be a boolean value returned:
level <= Math.Min(siblingContour.Keys.Max(), nodeContour.Keys.Max())
Finally, in a perfect world, I would love to see the x, modx values after these pats of the article:
1. …if we actually drew all the nodes at those X values, they would overlap and you wouldn’t be able to see the tree hierarchy.
2. …However it doesn’t stop the trees from overlapping each other. See nodes B, C, H, and I in our tree now
3. … After fixing middle trees after resolving a conflict.
4. …After Second Traversal of Tree
I know that must seem like a lot but I’m hoping wither you or others who have successfully translated them will help.
Appreciate,
John…
OK, making more progress I think. I revisited tree theory and I think I got the terms down now. And I think I have successfully mapped them into my brain.
However the contour dictionary, a seemingly simple tag, value pair is not returning the correct values I think. Most likely because I have not translated it correctly.
I have figured out how to convert the for loop. Would anyone be willing to work with me as I try and translate the CheckForConflicts routine? I’d like to cut my efforts from weeks to days (after many weeks to date).
Here’s how:
truegold AT isomedia dot com
Appreciate any help.
John…
Hey Rachel, I’m converting your routines to another language. I am making slow progress. My question is why do ‘GetLeftContour’ and ‘GetRightContour’ contain exactly the same code? Is it just so there’s a difference for name purposes? I’m a bit confused.
Appreciate,
John…
Hi John, one gets the left side of the tree using Math.Min, and the other gets the right side of the tree using Math.Max
Hi Rachel, OMG I have looked at those routines a dozen times and missed that distinction. Thanks for responding. Now back to pulling my hair out.
Hi Rachel,
I’ve translated/adapted this into JS for use in a hypertext fiction I wrote, wherein the tree is used to draw a map of interconnections between nodes. I didn’t see a license of any kind in the code – did you have a license in mind for when you released it? I’d love to be able to release my project under an open source license, but I don’t want to do so with code inspired by yours if you’d prefer to license/retain it otherwise.
Unfortunately I’ve gotten sidetracked by final debugging stuff and the intended release date (for the IFComp) is on the 28th, so I’d have to know fairly soon, or remove it.
Thanks so much,
furkle
Hi Furkle, you’re welcome to use my code. I never had any license in mind, but if I had to pick one it would definitely be Open Source Licensing. It’d be nice to have it attributed to me somewhere, but not necessary. Thanks for checking, and good luck! 🙂
Furkle, I was wondering, have you ever released this javascript adaptation of Rachel’s algorithm? If so, can you provide me with the link? Thank you!
Hello JSBoy, I have converted the above algorithm to JavaScript language. Tell me if you need the same
Hi. Nice job! I have a few comments, at least for the code I was looking at:
1) In CenterNodeBetween, the left/right nodes are switched on the first 2 lines of the method. Causes overlaps on some trees.
2) In CheckForConflicts, shiftValue should be the max of those found for each level whose contour is tested (shiftValue = Math.max(minDistance – distance, shiftValue). Causes odd gap behavior on some trees.
3) In CheckForConflicts the shiftValue should be applied outside the while loop otherwise you could shift right the node more than once if more than one level meets the sibling separation test. It should be shifted only for max shiftValue. Causes wide gaps on some trees.
This example tree will expose both issues if you haven’t done so yet:
Id = “TO”, ParentId = string.Empty
Id = “JW”, ParentId = “TO”
Id = “BK”, ParentId = “JW”
Id = “WH”, ParentId = “BK”
Id = “SE”, ParentId = “BK”
Id = “QI”, ParentId = “BK”
Id = “KX”, ParentId = “BK”
Id = “KA”, ParentId = “KX”
Id = “HH”, ParentId = “JW”
Id = “DN”, ParentId = “HH”
Id = “KT”, ParentId = “HH”
Id = “JB”, ParentId = “KT”
Id = “UM”, ParentId = “KT”
Id = “AL”, ParentId = “KT”
Id = “FR”, ParentId = “KT”
Id = “WE”, ParentId = “HH”
Id = “CO”, ParentId = “WE”
Id = “LE”, ParentId = “WE”
Id = “LO”, ParentId = “WE”
Id = “YI”, ParentId = “HH”
Id = “EI”, ParentId = “YI”
Id = “DJ”, ParentId = “YI”
Id = “SH”, ParentId = “YI”
Id = “BS”, ParentId = “JW”
Id = “SP”, ParentId = “BS”
Id = “SB”, ParentId = “JW”
Id = “GQ”, ParentId = “SB”
Id = “JS”, ParentId = “GQ”
Id = “HT”, ParentId = “SB”
Id = “MB”, ParentId = “HT”
Id = “MF”, ParentId = “HT”
Id = “FW”, ParentId = “SB”
Id = “GM”, ParentId = “FW”
Id = “XT”, ParentId = “FW”
Id = “VQ”, ParentId = “FW”
Thanks for the post. Very helpful. Hope you don’t mind my reply, meant to give something back. Thx again.
Thanks Carlos!
I recall I did notice bug #2 when I was working on this code, but never updated this blog post. I think I fixed it by storing the maximum distance a node needed to move on the node object model and applying it during one of the traversals. I don’t think I encountered the other bugs, but it’s good to know they exist for the future.
Regards,
Rachel
I confirmed all of the issues and fixes described by carlos with this data
sampleTree.Add(new SampleDataModel { Id = “O”, ParentId = string.Empty, Name = “Test GP O” });
sampleTree.Add(new SampleDataModel { Id = “N”, ParentId = “O”, Name = “Test Node N” });
sampleTree.Add(new SampleDataModel { Id = “F”, ParentId = “O”, Name = “Test Node F” });
sampleTree.Add(new SampleDataModel { Id = “E”, ParentId = “O”, Name = “Test Node E” });
sampleTree.Add(new SampleDataModel { Id = “2”, ParentId = “F”, Name = “Test Node F” });
sampleTree.Add(new SampleDataModel { Id = “B”, ParentId = “N”, Name = “Test Node N” });
sampleTree.Add(new SampleDataModel { Id = “A”, ParentId = “E”, Name = “Test Node A” });
sampleTree.Add(new SampleDataModel { Id = “D”, ParentId = “E”, Name = “Test Node D” });
sampleTree.Add(new SampleDataModel { Id = “Z”, ParentId = “E”, Name = “Test Node D” });
sampleTree.Add(new SampleDataModel { Id = “Y”, ParentId = “A”, Name = “Test Node A” });
sampleTree.Add(new SampleDataModel { Id = “Q”, ParentId = “A”, Name = “Test Node A” });
sampleTree.Add(new SampleDataModel { Id = “U”, ParentId = “D”, Name = “Test Node A” });
sampleTree.Add(new SampleDataModel { Id = “W”, ParentId = “D”, Name = “Test Node A” });
sampleTree.Add(new SampleDataModel { Id = “R”, ParentId = “Z”, Name = “Test Node D” });
Great blog Rachel!
I was just wondering if you could update the source code with this changes.
Thanks you very much.
Hi Carlos, thanks for finding these, my graph is suffering from them. I’m not sure how the final CheckForConflicts method should look like with your fixes. Can you post the fixed version? Appreciate it if you can.
You have some really great posts on here. Thanks.
Would you please provide us the sample source ?
The sample code can be downloaded here (also linked at the end of the article) 🙂
Hi, source link is not valid, could you fix it please?
Hi Jedr, I just tested and it seemed to work OK. It goes to a location on Google Docs, and there’s a Download icon in the top middle of the page to download a copy.
Thanks a lot Rachel , for all the basics you’re covering in a very clear yet accurate manner. the amount of pain WPF is giving me came down from generalized organ failures to a good old fashioned punch in the face.And for that i must thank you.