1
$\begingroup$

In programming say you have a boolean tree like this:

a(
  b(c(), d(), 
    e(h(), i(j(), k(l()))), 
    f(m(), n(p(), q()), o()),
    g()
  ),
  r(),
  s(t(), u(), v(w(), x(y(z()))))
)

Each function is different, they all can accept arbitrary number of arguments, and they return $\rightarrow \{1,0\}$ a boolean value.

Then there is an algorithm that gets all the leaf nodes, so mathematically we can say:

$$ l = N \rightarrow L' $$

where $l$ is a "leaf" function mapping all the nodes $N$ to a subset of nodes $L \subset N$.

Finally, there is a "calculate the final boolean value for the tree" function that starts at the leaf nodes and works its way up to the top.

What I'm wondering is how to define that last part mathematically.

  1. How to define the tree that can take into account arbitrary tree structures with arbitrary number of children at each node.
  2. That iterates through the nodes starting from the leaf nodes, then to the parent nodes, then to the parents, until it gets back to the top.

This is as far as I've gotten but don't think it's right.

$$ t = n + (t_0,\dotsc,t_i)? $$

where $t$ is a tree and $n$ is a node, and $?$ means it's optional. Trying to capture the recursive nature of it.

Procedure:

$$ Start\ at\ leaf\ nodes\ l : N \rightarrow L $$ $$ Calculate\ value\ v \in \{0,1\} $$ $$ Collect\ all\ the\ children\ to\ sum\ their\ value\ V $$ $$ Repeat\ for\ the\ next\ parent $$ $$ Finish\ when\ at\ top. $$

I am new to algorithms and writing them mathematically, so this is probably a beginner question.

$\endgroup$
  • $\begingroup$ Why do you want to start at the leaf nodes, rather than the root? If you start at the root, the corresponding recursive algorithm is easy to write. $\endgroup$ – NietzscheanAI Apr 3 '18 at 7:25
  • $\begingroup$ It looks to me like your concept of 'leaf' is not exactly as desired: the mapping l is probably intended to return the child nodes of a given node, which are not necessarily leaves of the entire tree. $\endgroup$ – NietzscheanAI Apr 3 '18 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.