# How to construct a specific binary tree from a particular set of information?

I run a algorithm to solve a problem that return a set of information relative to a binary tree associated with these problem. For illustrate the results obtained I try to plot the binary tree. I make the plot of the right in image below. But I like to plot the tree of the left.

The question is: How plot the binary tree of right in figure below?

The input data for this is two lists. The first contain the "path" of solution (for the tree in the left/right below: paths = {{0, 0, 0, 0, 0}, {0, 1, 1, 1}}) the second list contain the number of nodes in each level (for the tree in the right below: nodes_leves = {1, 2, 4, 4}).

I tried search for the functions associated with graph, trees, etc. but don't encountered a solution for plot this specific tree.

Thanks in advance

Explanation of "paths":

First, denote the "path" {0, 0, 0, 0} for {a = 0, b = 0, c = 0, d = 0}. For the level 1 we have one possibility. Then the a = 0 is the node root. The partial path in the binary tree so far is {left} (see the picture below).

After this we have two possibilities for b. But the solution is b=0. That is, in the path we have chosen the left. So far the path in the binary tree is {left, left} (see the picture below).

Note that in second level is possible to have {left, rigth}, i.e., {a = 0, b = 1}. But for the "path solution" the path chosen is {left, left} = {0, 0} = {a = 0, b = 0}.

For the third level we have the possibilities {left, left, 'left/right'}. But the solution is {left, left, left}, i.e., {a = 0, b = 0, c = 0} or {0, 0, 0}. The picture below illustrate this.

And follow this construction we have the two paths solutions in the binary tree: {0, 0, 0, 0} = {left, left, left, left} and {1, 1, 1, 1} = {right, right, right, right}.

The node root maybe be green. But its not fundamental. The problem is receive from input: any path, for e.g. {0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1}, where "0 is choose node son of left" and "1 is choose node son of right" in a certain level, and the number of nodes in each level, for e.g. {1, 2, 4, 2, 8, 5, 4, 3, 2, 4, 4, 4} and plot the respective binary tree with the "paths" and the nodes deleted.

We are going down in this binary tree. In level 1, we have 1 node. In level n we have $$2^n$$ nodes (in the worst case).

• Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour and check the faqs! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! – Dunlop Sep 13 '19 at 19:10
• can you explain how paths = {{0, 0, 0, 0, 0}, {0, 1, 1, 1}} is related to the two trees? – kglr Sep 13 '19 at 22:10
• Thanks, @kglr! Your answer below, don't includes the paths in the tree. For e.g. for the path $\{0,0,0,0,0\}$ in each choice in the binary tree, the vertice of left is choosen. '0' indicate left and '1' indicate the rigth (son) in this binary tree. Is it possible include this in the code for the plot? – user78008 Sep 16 '19 at 11:22
• user78008, still don't understand how {0,0,0,0,0} (a list with 5 elements) relates to the verbal description "in each choice in the binary tree, the vertice of left is choosen" (there are 7 such choices in the left tree). I added new pieces in my answer for highlighting selected edges. – kglr Sep 16 '19 at 15:22
• I edited the question for explain whats means the "path" in the binary tree. The correct is {0, 0, 0, 0}, a list with $\underline{4}$ elements (were a typo). – user78008 Sep 17 '19 at 2:20

## 1 Answer

You can use CompleteKaryTree to construct the left tree and process it to remove unwanted nodes to get the right tree:

leftg = CompleteKaryTree[4,2,
ImageSize -> 300,
VertexStyle -> {_ -> Blue,  Alternatives[2,4,8,3,7,15]-> Green}];

rightg = VertexDelete[leftg, Range[10, 13]];

Row[{leftg, rightg}, Spacer[10]]


Highlighting edges:

In each choice in the binary tree, the vertex on left is chosen

HighlightGraph[leftg, First /@ GatherBy[EdgeList[leftg], First]]


In each choice in the binary tree, the vertex on right is chosen

HighlightGraph[leftg, Last /@ GatherBy[EdgeList[leftg], First]]


In the first node the left branch is chosen and in other nodes right branch is selected

HighlightGraph[leftg, {#[[1, 1]], #[[2 ;;, -1]]} & @ GatherBy[EdgeList[leftg], First]]


Alternatively, instead of deleting you can hide unwanted vertices and the edges leading to them using the options VertexShapeFunction and EdgeShapeFunction

SetProperty[leftg,
{VertexShapeFunction -> {Alternatives @@ Range[10, 13] -> None},
EdgeShapeFunction -> {Alternatives @@ IncidenceList[leftg, Range[10, 13]] -> None}}]


or using the options VertexStyle and EdgeStyle:

SetProperty[leftg,
{VertexStyle -> {Alternatives @@ Range[10, 13] -> Directive[EdgeForm[], White]},
EdgeStyle -> {Alternatives @@ IncidenceList[leftg, Range[10, 13]] -> White}}]


same picture

• Thanks for help, but this not answer my question. – user78008 Sep 18 '19 at 14:24