Binary Tree: Force lonely node to be left or right

[ElectricHamster]

Hey guys,

Im trying to make a binary tree with Graphviz (dot).
This is my simple code so far:

graph{
	node [shape=circle]
    1 -- 2;
	2 -- 5;
	2 -- 4;
	5 -- 7;
	7 -- 6;
	6 -- 13;
	13 -- 11;
	11 -- 12;
	12 -- 14;
	4 -- 8;
	4 -- 3;
	3 -- 9;
	9 -- 10;
    
}

And this is the ouput:

So what I want to get is that for example node 2 is the left child from node 1, and node 7 is the right child node of node 5.

I tried it with “empty” nodes (style = none, color = white) but it still had those straight downward edges.
I want it to look like a nice and smooth binary tree, where you can see what is a right and left child (even if the child is single).

Hope you can help me to get this style I want

Thank you

[steveroush]

Would you sketch out what you are looking for - by hand is fine. (If you wanted a classical tree shape, it might be ~128 nodes wide)

[ElectricHamster]

This is what I want (didnt draw all nodes I need)
You see, in this tree clearly left and right nodes. Even if the nodes have no siblings.

In the tree I created with dot the edges are straight downward. And I need left and right nodes everytime.

[steveroush]

Unfortunately, Graphviz does not include a tree model (see How to lay out binary tree / hierarchicy? - #3 by steveroush and Provide a collection of simple tree layouts (#2032) · Issues · graphviz / graphviz · GitLab).
However, here is a post-processor program for binary trees (not well tested). It is pretty simple-minded, defaulting to single-edges-always-go-left rule. (single-edges-always-go-right is equally easy). The problem with these simple rules is that they tend to be very lop-sided (see bottom).
To allow for more symmetric layouts, the post-processor allows the user to explicitly direct an edge right or left using a new edge attribute: side. Values: L|l|R|r|U|u|D|d
The post-processor is written in the GVPR (https://www.graphviz.org/pdf/gvpr.1.pdf) language - part of the Graphviz package. The GVPR output is passed to neato -n (see FAQ | Graphviz). Somewhat convoluted, but you should not have to mess with anything other than your input.
Command-line (Linux) (Windows should be similar):
dot -Tdot myfile.gv | gvpr -c -f binaryTree.gvpr | neato -n -Tpng >myfile.png

binaryTree.gvpr:

BEGIN{
 int left_right, Right[], Left[];
 float shiftFactor;
 node_t Head, Tail;
}
BEG_G{
  left_right=0;
  if ((hasAttr($G, "rankdir")) && ($G.rankdir!="") && $G.rankdir=="@(LR|RL)") left_right = 1;
  shiftFactor=1.1*72; // effectively sets the angle (eyeballed, no trig)
}
E{
    Head=$.head;
    Tail=$.tail;
    // legal values for side: left(L|l) or right(R|r) or up(U|u) or down(D|d)
    // current value testing is incomplete
    // awkwardly written, but seemingly correct
    if (Left[Tail]!=1 && (((!((hasAttr($, "side")) && ($.side!=""))) || Right[Tail]==1 || ((hasAttr($, "side")) && ($.side!="") && $.side=="@(L|l|D|d)")))){
      print("// LEFT/UP");
      Left[Tail]=1;
      if (left_right==0)
        Head.pos=(string)(Tail.X-(shiftFactor*(float)Head.width)) + "," + (string)Head.Y;
      else
        Head.pos=(string)Head.X + "," + (string)(Tail.Y-(shiftFactor*(float)Head.height)) ;
    }else{
      print("// RIGHT/DOWN");
      Right[Tail]=1;
      if (left_right==0)
        Head.pos=(string)(Tail.X+(shiftFactor*(float)Head.width)) + "," + (string)Head.Y;
      else
        Head.pos=(string)Head.X + "," + (string)(Tail.Y+(shiftFactor*(float)Head.height)) ;
    }
  $.pos="";
}

Your file, modified:

graph{
  node [shape=circle]
  1 -- 2;
  2 -- 5;
  2 -- 4;
  5 -- 7;
  7 -- 6;
  6 -- 13 [side=R]    // added a new attribute (side), send this edge to the right
  13 -- 11;
  11 -- 12  [side=R]   // this edge to the right
  12 -- 14;
  4 -- 8;
  4 -- 3;
  3 -- 9;
  9 -- 10 [side=R]    // this edge to the right
}

Giving:

Default (lop-sided) version from the program:

[lu5m]

thank you for your great work!
however, i encounter a overlapping problem like below, how to solve?

graph {
    node [shape=circle];  
    a--b;
    b--d;
    d--g [side=R];
    b--e [side=R];
    a--c [side=R];
    c--f;
}

[steveroush]

First an answer to your question:

graph {
    node [shape=circle];  
    a--b;
    b--d;
    d--g [side=R];
    b--e [side=R];
    a--c [side=R];
    c--f [side=R]  //  flipped to the right side
}

Giving:

I’ve been laughing at my program all morning. Note that I did say:

(not well tested). It is pretty simple-minded

This program is very simple-minded and not even close to being a general-purpose binary-tree program. OK for some sparse binary-trees, but that is it. (Think about the case of B and C each having two children).
I assume that somewhere there good heuristics for this problem. Maybe sometime one will be coded up for Graphviz.

[lu5m]

inspired by Visualising a Binary Search Tree using GraphViz « devjeetr , got a simpler solution.

• adding empty nodes( shaped as point) to represent empty siblings;
• relying on graphviz to handle the possible overlapping issue.
• not as pretty as above, but simple and sufficient.

graph {
node [shape=circle]; 
	a--b;
	b--d;
	d_NULL_LEFT [shape=point];
	d--d_NULL_LEFT;
	d--g;
	g_NULL_LEFT [shape=point];
	g--g_NULL_LEFT;
	g_NULL_RIGHT [shape=point];
	g--g_NULL_RIGHT;
	b--e;
	e_NULL_LEFT [shape=point];
	e--e_NULL_LEFT;
	e_NULL_RIGHT [shape=point];
	e--e_NULL_RIGHT;
	a--c;
	c--f;
	f_NULL_LEFT [shape=point];
	f--f_NULL_LEFT;
	f_NULL_RIGHT [shape=point];
	f--f_NULL_RIGHT;
	c_NULL_RIGHT [shape=point];
	c--c_NULL_RIGHT;
}