Generate coordinates for each node to display a complete binary tree?

Questions
1

Hello,

I have a data structures problem, and since I am using Three.js for the program, I thought I would ask here first.

Given the root of a complete binary tree and the height, how can I position the nodes on an XY Grid so that there is no overlap?

image
image774×322 20.5 KB

The idea is that each node has an XY coordinate and can be displayed as a box on the screen.

I tried doing an inorder print, but the nodes on the left would overlap the nodes on the right.

function inOrderPrint(node, x, y, depth, maxDepth) {
  if (node === undefined) {
    return;
  }
  console.log("(X,Y): " + x + ", " + y)
  let boxMesh = new three.Mesh(new BoxGeometry(1, 1, 1), new three.MeshBasicMaterial())
  boxMesh.position.x = x;
  boxMesh.position.y = y;
  scene.add(boxMesh)
  inOrderPrint(node.getLeft(), <Some decrease of x>, y - 2, depth + 1, maxDepth);
  inOrderPrint(node.getRight(), <Some increase of x>,y - 2, depth + 1, maxDepth)
}

The root is at 0,0, and nodes to the left decrease in x, while nodes to the right increase in x.

If the tree is complete and the height is known ahead of time, what equation should I use to set the exact x value of a given node?

Should I be using breadth search instead?

2

Absolutely not! The coordinates of each node can be calculated directly. See this demo and change the tree height in line 63 (the coordinates of each node are calculated in lines 74-75):

https://codepen.io/boytchev/full/vYVowVG

image

3 Likes
3

Thank you, that is a good example of what I am looking for.

var p = 2**(HEIGHT-y-1);
var px = 15*( p/2 + x*p - 2**(HEIGHT-2) - 1 ),py = 50 - 15*y;

Could you explain the source of these equations?

4

image
image957×312 11.8 KB

Look from bottom to top (from leaves to root). Here are some observations when you move from one row to the upper row:

  • the bottom row has offset 1 of the first node (blue arrow) and gap 2 between nodes (red arrows)
  • when you go to the upper row, the offset and the gap double

So, in the equation you have several powers of two, but because levels are measured in the opposite direction, it is not 2y, but 2height-y-1. Here is how I built the expression:

  1. horizontal position is equal to 15.x, all nodes are equally distributed
  2. making the horizontal gap p=2height-y-1 will expand the gap depending on the row, so now the position of nodes is 15.x.p
  3. adding the initial offset makes the position 15.( p/2 + x.p )
  4. the last step it to shift everything to the left, so the root is centered at position 0, this is what -2height-2-1 does

image
image1394×936 119 KB

3 Likes