How to minimize visual width of (binary) search tree?

Question

Introduction

I'm building an HTML5 web application that creates a visual representation of a binary search tree from a given list of numbers.

Currently, I have an algorithm which calculates the visual spacing between nodes on each row based on the maximum depth of the tree (which is a base-0 value):

offset = 50
offset *= pow(2, maxDepth - currentDepth)

From here, the position of the node is determined using this offset and the x-position of its parent.

The algorithm works well, because it's always able to accommodate for the widest-possible tree of any depth. However, this also makes the tree unnecessarily wide at times.

Examples

Tree branching to the left (too wide):

Tree branching to the left http://f.cl.ly/items/0c0t0L0L0o411h092G2w/left.png

Tree branching to both sides (left and right sides could be closer together).

Tree branching to both sides http://f.cl.ly/items/0r3X1j0w3r1D3v1V1V3b/left-right.png

Ideally, the above tree should be shaped like a pyramid, with a smaller width and with the sides straight, as depicted below:

Balanced tree (case where the algorithm works best):

Balanced tree http://f.cl.ly/items/203m2j2i3P1F2r2T3X02/balanced.png

Implementation

Properties

I'm using Backbone.js to create nodes from a Node model. Each node has the following properties:

• parent (the parent node)
• left (the left child node)
• right (the right child node)
• x (the x-position of the node in pixels)
• y (the y-position of the node in pixels)

The x and y properties above are calculated based on the direction the node branches from:

if (parent.get('left') === node) {
    x = parentX - offsetX;
    y = parentY + offsetY;
} else if (parent.get('right') === node) {
    x = parentX + offsetX;
    y = parentY + offsetY;
}

At this point, the x and y properties are the exact values used to position the nodes (each is positioned absolute within a container element).

Methods

• getDepth() (returns the base-0 depth of a node)
• getMaxDepth() (returns the depth of the last row in the tree)
• getRow(n) (returns an array of all nodes at depth-n)

Question

Therefore, my question is simple:

What is the best algorithm to minimize the aesthetic width of my binary tree?

Answer 1

It could help you if you looked at the answers given to a similar question; they contain links to software doing exactly the kind of tree visualization that you want.

---

Aesthetics is highly subjective, so this is just my opinion. I think my guidelines (not an algorithm) would be the following. I am assuming that the order of children is important (as these are binary search trees).

1. Only x coordinates are interesting; y coordinates should only be determined by the node's level. (I would find it rather ugly if this was violated but, as I said, tastes differ. However, the rest is based on this assumption.)

2. No nodes in the same level should be closer than some fixed minimum distance (say D).

3. If a node has two children at x1 and x2, I would prefer it to be placed at (x1+x2)/2. In some cases, it would be preferable to select some other coordinate in [x1..x2] (possibly one of its ends). I guess there could be unusual cases where a coordinate outside [x1..x2] would be preferable.

4. If a node has one child at x1 and its parent is at xp, I would prefer it to be placed at (x1+xp)/2 (so that it lies on the line connecting its parent to its child). In some cases, it would be preferable to deviate from this and select some other coordinate in [xp..x1] (or even outside).

5. Let's call width of a level the distance between the leftmost and the rightmost node. The width of the widest level should be minimal.

These guidelines impose constraints that cannot be satisfied all at the same time. Therefore, you should prioritize them, and this is again subjective. E.g., what's more important, #4 or #5? Your sketch for the 5-node tree implies that #4 is more important; if #5 was more important you'd get a house-like picture (vertical lines); if both were important, then your current result would be fine.

One way to tackle this is by assigning weights to the guidelines and define penalties if these are not followed. E.g., in guideline #3, you could and penalize with abs(x-(x1+x2)/2) if a parent is placed at x which is not halfway between its children; you could also assign a weight that tells you how important this is, in comparison with other guidelines. You should then try to minimize the total weighted penalty of the solution. In general, this would give you a constraint optimization problem and there are several ways to solve such problems.

Answer 2

You can use an AVL tree. These self-balance on insertion giving you a balanced tree after every insertion.

http://en.wikipedia.org/wiki/AVL_tree