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

Question

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?

Adding example

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".

Answer 1

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].