Binary Trees are a very useful tool in computer science. At one point I was given a task that required drawing out a proper binary tree, which is defined as "a tree in which every node in the tree has either 0 or 2 children". I discovered soon enough that that wasn’t as simple as it would first appear. Research on the web wasn’t too promising at the time, with none proving ideal for a proper binary tree. I have since found these two articles:
I remember reading another suggestion that would use some elasticity of the lines to try and move everything as closely as possible. I was not happy with that idea; the example shown had a tendency to have the nodes wobble after they had gotten into nearly their place. It would also be hard to develop and not predictable.
I went through several iterations of research before I found an acceptable way to draw a tree. My basic principle was that it had to look good. But that is hard to codify, so I will attempt to do that here with what I learned.
The first lesson I took was spacing. For simplicity, I would imagine the tree overlaid on a grid. This would aid in positioning things so that they would line up nicely. Unfortunately it became clear that this would cause the tree to spread out quickly and unattractively.
A better approach was to try and make it so that a node with two leafs would form an equilateral triangle, as you can see here:
The equivalent tree with this method would look like this:
That looks much tighter and nicer. Since we still want to have the nodes placed just anywhere, I would still place the nodes on a grid, but the X-axis would be squished enough that they would form the equilateral triangle. As a consequence, I was left with the requirement that no adjacent nodes could be closer than two increments to each other, and children could be within one increment of their parent.
This is the result of an algorithm where everything is left-aligned. It is fast, but it looks terrible.
If you click on any of the red leaf nodes, they transform into a branch and redraw, so you can experiment with how this tree would look.
The first step in positioning the nodes is to start with a simple rule: The parent has to be to the right of its left node and left of its right node.
That seems simple enough, so what is the best way to implement that?
The method I used was to have an array that is filled in as the algorithm goes through the tree. The array keeps track of the last position filled on that level. This allows us to quickly keep track of what positions are still available. Then it can recursively go through the tree and apply these rules.
First we let the left nodes figure out their positioning. Then the parent node is enforced to be to the right of that. Then the right nodes have to be to the right of that. After the right node has been positioned, we can even add an adjustment to the parent so that it is in-between the two child nodes.
This is the algorithm that I came up with to enforce that.
/** * This method recursively positions the tree nodes into a balanced tree. * @param {Number|Array} nextAvailablePositionAtDepthArray An array to track what is the leftmost position still available at any depth. * @param {Number} leftMargin The leftmost position that this node is allowed to be in. This is used to enforce that the right node is to the right of the parent. * @param {Number} depth The current depth in the tree * @returns {Number} X position used */ TreeNode.prototype._calculateTreeNodePositionsWithBalancedParent = function(nextAvailablePositionAtDepthArray, leftMargin, depth) { // Assert that the nextAvailablePositionAtDepthArray array has an entry for the current depth. if (nextAvailablePositionAtDepthArray.length <= depth) { nextAvailablePositionAtDepthArray[depth] = 0; } this.yPos = depth; //By default, the x position is has to be at least as left as both the given left margin and the leftmost position available. this.xPos = Math.max(nextAvailablePositionAtDepthArray[depth], leftMargin); if (!this.IsLeaf()) { // Recursively set the left tree, which can be as far left as the nextAvailablePositionAtDepthArray allows var leftPos = this.left._calculateTreeNodePositionsWithBalancedParent(nextAvailablePositionAtDepthArray, 0, depth+1); // After calculating the positioning of the left nodes, we need to make sure our parent node is to the right of it. this.xPos = Math.max(this.xPos, leftPos+1); // Recursively set the right tree, which has to be to the right of the parent node var rightPos = this.right._calculateTreeNodePositionsWithBalancedParent(nextAvailablePositionAtDepthArray, this.xPos+1, depth+1); // Try and center the middle node if possible. This is a simple adjustment that helps the tree look nice var midPos = Math.floor((leftPos + rightPos) / 2); if (midPos > this.xPos) { this.xPos = midPos; } } // Update the nextAvailablePositionAtDepthArray now that we have decided the X position of the node. nextAvailablePositionAtDepthArray[depth] = this.xPos + 2; return this.xPos; };
With this algorithm, this is the result.
It looks fairly nice, and it is a good first step. But you can see the start of some issues. It is more obvious with this example:
The problem is that the algorithm is still left justifying things whenever it can, as long as it follows the rule. This will need to be fixed.
For the third algorithm, we will add another rule: The child nodes should be as close to their parent as possible.
Now how do we implement that?
What you can quickly notice is that the right branches all seem to follow that rule already. The only problem is that the left branches have more attraction to the left margin than their parent. However, we can use that behaviour to our advantage. Since everything is as far left as possible, the right children are already as close as possible to their parent. All that remains is to move the left children as far to the right as possible, without moving any of the right children. We can do that after we have performed the previous algorithm.
To do this, we essentially do the reverse process that we did for the second algorithm. Now we will go through the tree again, recursively, but starting with right nodes. We keep track of where the right nodes are placed. Then when we get to the left nodes, we calculate how far they can be shifted to the right safely, keeping track in an array to the depth of the left tree. We can then use the minimum value in that array to determine the amount we can shift. (If a level claims it can be shifted three nodes over, we still can’t if its children can only be shifted one node only.)
If the amount we can shift is non-zero, recursively shift the left branch, and update the array we pass to the parent, in case it wants to shift the current tree as well.
Since this is the last operation we are doing, we can also explicitly centre the current node between its two children, if space allows.
This is the algorithm that I came up with to do that.
/** * This method moves left branches as far right as they can legally go.. * @param {Number|Array} lastUsedPositionAtDepthArray An array to track what is the last right position used. * @param {Number} depth The current depth in the tree * @returns {Number|Array} An array of how much each level can be safely shifted to the right */ TreeNode.prototype._shiftLeftNodesRight = function(lastUsedPositionAtDepthArray, depth) { var result; if (!this.IsLeaf()) { // Go through the right nodes and get information of how far it could be shifted to the right. This // will not be used and is to be returned to the caller. var rightInfo = this.right._shiftLeftNodesRight(lastUsedPositionAtDepthArray, depth+1); // Go through the left nodes and get information of how far those nodes can be shifted to the right. var leftInfo = this.left._shiftLeftNodesRight(lastUsedPositionAtDepthArray, depth+1); // How far can the current node be shifted to the right, assuming it doesn't conflict with an existing node and // is still to the left of the right node. var currRightLimit = Math.min(lastUsedPositionAtDepthArray[depth] - 2, this.right.xPos - 1); var currLeftLimit = this.xPos; // The current node is already at its furthest left limit // Get the minimum distance the left nodes can be shifted. var leftMin = Math.min.apply(null, leftInfo); // How far can the left nodes be shifted, while still being to the left of the current node's rightmost limit var leftDeltaPossible = Math.min(leftMin, currRightLimit - 1 - this.left.xPos); // If there is space, shift the left nodes as much as possible. if (leftDeltaPossible > 0) { this.left._shiftTree(leftDeltaPossible, lastUsedPositionAtDepthArray, depth+1); } // Determine the ideal position for the current node, in between its two branches. This is where // we may get non-integer value, but since we will be done calculating positions after this, it // is acceptable. var idealCurrPosition = (this.left.xPos + this.right.xPos) / 2.0; this.xPos = _clamp(currLeftLimit, idealCurrPosition, currRightLimit); // Replace the leftInfo with the rightInfo, up to the depth of the right info. // Subtract slide from leftInfo var i; for (i = 0 ; i < rightInfo.length; i+=1) { leftInfo[i] = rightInfo[i]; } for (i=i ; i < leftInfo.length; i+=1) { leftInfo[i] -= leftDeltaPossible; } result = leftInfo; } else { result = []; } // Add current level to the result result.unshift(lastUsedPositionAtDepthArray[depth] - 2 - this.xPos); // Update lastUsedPositionAtDepthArray with this level's information lastUsedPositionAtDepthArray[depth] = this.xPos; return result; }; function _clamp(min, num, max) { return Math.max(min, Math.min(num, max));}
The lastUsedPositionAtDepthArray is initialized with an array the size of the depth of the tree and set to the absolute width of the tree.
With this algorithm, this is the result.
And that looks good!
If you wish to play around with the algorithm, you can go to my playground page. It displays a very simple tree. If you click on any red leaf node, it will automatically change it to a new branch, and reposition all the other nodes as per the algorithm.
I have placed the Javascript file that I use to show all of this on GitHub. If you would like to download it, you can find it in my AdHavocBinaryTree repository.
2016-1-30: Inital writing
2016-5-15: Rewrote the javascript to use CSS and make the UI of the tree more intuitive.