# Construct a binary tree where nodes are labeled according to given rule

I want to plot a binary tree in Mathematica where the nodes are labeled according to a given rule. In fact, whether a node has a left child or a right child or both, will be determined by a rule. And then I want to label each node according to some rule as well. How do I do that? I can accomplish this rather simply in programing languages such as Java/Kotlin. But Mathematica offers the advantage of a nice drawing and that's what I want (plus the rules are mathematical equations, etc.) How might I achieve this?

By way of example, let's imagine it's a BST and a random function is generating the values. And the label of each node is a randomly chosen letter followed by the order in which that node was added, like "c7".

• "...whether a node has a left child or a right child or both, will be determined by a rule. And then I want to label each node according to some rule as well." - it would be nice if you could give a concrete example of what you have in mind. May 8, 2020 at 2:53
• I've edited to specify an example. Does that help? May 8, 2020 at 3:36
• related Q/A: How to really plot a binary tree?
– kglr
May 8, 2020 at 5:37

I want to plot a binary tree

The solution I will present is specifically for visualization. It is not for constructing a data structure usable as a binary tree.

The following makes use of IGExpressionTree from my IGraph/M package, version 0.4 of which is compatible with Mathematica 10.0 and later. Something similar could be implemented with ExpressionGraph, available in Mathematica 12.1 and later only.

Needs["IGraphM"];

i = 0;
makeVertex[] := RandomChoice@CharacterRange["a", "z"] <> IntegerString[i++]

treeNode[] := If[RandomReal[] > 1/2, makeVertex[], Null]

i = 0;
tree = FixedPoint[
Replace[#, s_String :> s[treeNode[], treeNode[]], {-1}] &,
makeVertex[]
];

g = IGExpressionTree[tree];

HighlightGraph[g,
Subgraph[
g,
Pick[
VertexList[g],
First /@ IGVertexProp[VertexLabels][g],
_String
]
],
GraphHighlightStyle -> "DehighlightHide"
]


And the label of each node is a randomly chosen letter followed by the order in which that node was added

makeVertex does this.

whether a node has a left child or a right child or both, will be determined by a rule

This is the rule: s_String :> s[treeNode[], treeNode[]]. treeNode[] has a 50% change of being Null, which I used to represent no vertex. More precisely, no children will be added to Null, and it will be present in the final tree, but hidden. This is necessary to ensure that left/right children are drawn leftwards/rightwards, even if there is just one of them.

IGExpressionTree generates convenient vertex labels for us. We use these to identify which vertex is Null, and therefore needs to be hidden. IGExpressionTree wraps vertex labels in HoldForm, which is why we need First in First /@ IGVertexProp[VertexLabels][g]`.