In this post, I’ll lay out a simple algorithm which can be used to draw binary trees – it can be extended to draw other tree types as well. To be clear, a binary tree is a tree data structure in which each node has at most two children (Wikipedia).
As is convention, we’ll be drawing the tree top-down with the root at the top and I’ll use “left” and “right” to designate the left and right children of a node respectively. To make things easier, let us assume each node has a fixed diameter, d. We also want each node in the same level of the tree to be centered at the same vertical position, so we’ll define h to represent the separation between levels. Finally, we want subtrees to be at a distance w from each other (assume w is always greater than d). The following diagram clarifies the convention I’ve chosen.
Notice that I’ve drawn boxes around the nodes. I’ll refer to those as bounding boxes and you’ll understand their usage shortly.
In order to position a node, we need to know how large its children are so that we can center it. This naturally tends to recursion because to know how large a child is, we will need to know how large its children are also and so on till we get to a leaf node whose size is d x d. We will use the width and height of a bounding box to represent this size. Do remember that the bounding boxes of the left and right children are separated by a distance w.
In other words, we need to do a post-order traversal of the tree and in each step, we obtain the size of a sub-tree. If you’re not familiar with it, this means you visit the left node first, then the right node and then the current node (L-R-C). Here’s the pseudocode:
function setSize() : void if left is not null then left.setSize() if right is not null then right.setSize() if both children are not null then width = left.width + w + right.width height = h + max(left.height, right.height) else if left is not null then # left child only width = left.width + (w + d) / 2 height = left.height + h else if right is not null then # right child only width = right.width + (w + d) / 2 height = right.height + h else # leaf node width = height = d end if end function
As an illustration, consider the diagram above. The labels indicate the order in which the bounding rectangles are measured.
- At the root, you call left.setSize() which then calls left.setSize() and finally we get to node H. Since H is a leaf node, it’s size (width x height) is d x d.
- Since D has no left node, we add half the separation and half the diameter to get its width. It’s height is simply H’s height + h.
- Since this is a post-order traversal, the next node to measure is E and since it’s a leaf node, it’s size is also d x d.
- The width of B is then sum of the widths of it’s sub-trees and w and it’s height is the greater of the heights of its children plus h.
- We then go to the right sub-tree of A (the tree rooted at C). This calls left.setSize() and since F is a leaf node, it’s size is d x d.
- At the right of C is G and we go to it’s left I which is a leaf node – d x d.
- The size of G is calculated in a fashion similar to that of D
- C’s size is calculated similar to B’s.
- A’s size (which is the size of the tree) is calculated in a manner similar to B.
Positioning and Drawing
Once the tree’s size has been accurately determined, the next step is to position and draw each node. The algorithm we use here assumes that the x and y coordinates of the center of the current node is specified. Using this information, we then figure out how to place the children so that the current node appears to be in the middle of it’s bounding box.
Here’s a summary:
- If a node has a left child only or right child only the horizontal distance between the center of the node and that child (w + d) / 2
- If it has both children, then the placement of the children, depends on the placement of nature of the subtree rooted at its children.
- If the child has both children, then place it such that it is centered in its bounding box.
- If it has a single child, then it should be positioned at either the left or right end of its bounding box depending on which child it has (see image above for clarification.
- If it a leaf, center it in its bounding box.
function drawNode(x: real, y: real) # draw this node if both children are not null then # next level is h below current childY = y + h # center both children in their bounding boxes # left end of bounding box leftStart = x - width if left has both children then leftX = leftStart + left.width / 2 else if left has a left child then leftX = leftStart + left.width - d / 2 else leftX = leftStart + d / 2 # position at top-left of bounding box end if # right end of bounding box rightEnd = leftStart + width if right has both children then rightX = rightEnd - right.width / 2 else if right has a right child then rightX = rightEnd - right.width + d / 2 else rightX = rightEnd - d / 2 end if left.drawNode(leftX, childY) right.drawNode(rightX, childY) # draw lines connecting the children to the current node else if left is not null then leftX = x - (w + d) / 2 left.drawNode(leftX, childY) # draw line connecting left node to this node else if right is not null then rightX = x + (w + d) / 2 right.drawNode(rightX, childY) #draw line connecting right node to this node end if end function
Finally, since we all love to see proofs of concept, here’s a GitHub repository that demonstrates a working version of the algorithm implemented in C# using WPF. I hope you found this to be helpful!