How to write a summation function that counts the number of nodes in a tree?

Question

I come from a programming background and am interested in learning how to represent some things as simple equations, as an entry into thinking mathematically.

How do you represent a tree structure as a function/equation, where the function recursively counts the number of nodes in the tree? How would you go about writing that?

An example would be to have an equation that stands for a tree of HTML nodes, so you can use that to reason about how many HTML nodes are on a web page in an abstract way.

An example HTML tree might look like this:

<section>
  <header>
    <hgroup>
      <h1></h1>
      <h2></h2>
    </hgroup>
  </header>
  <div>
    <p>
      <span></span>
      <span>
        <em></em>
      </span>
      <a>
        <img>
      </a>
    </p>
    <ul>
      <li>
        <a></a>
      </li>
      <li>
        <a></a>
      </li>
      <li>
        <a></a>
      </li>
    </ul>
  </div>
</section>

The equation would work something like:

sum(tree) == 19

All that's important for this first equation is to be able to count the number of nodes in the tree, it doesn't matter what they are. Once I sort of understand how you might an equation for something like that, I am interested in asking some follow up (separate) questions about keeping track of node type and stuff like that.

Thanks for the help! Looking forward to starting to look at things with a more mathematical eye.

Edit

I am looking for how to represent this as an equation, so I can learn to think about and write things mathematically. I am looking for:

• How do you go about defining the variables? For this, is it like {V} is the set of all nodes/vertices? Stuff like that (I don't know how to do this which is the reason for asking).
• How do you write an equation that describes this system (the tree of vertices V or whatever)?

If it can't be written as a single equation, maybe it can be written as multiple equations. Something along these lines (just took a snippet of some equation from Diestel's Graph Theory Book, this equation is totally random haha, but I am looking to write something along these lines if possible):

The major reason for asking is, I have been trying to read books about graph theory for a while, and they have many equations, which I am beginning to understand. But the problems they go into are never close enough to heart, so it's still not intuitive. So I'm thinking, try something that is with HTML because that is where I do a lot of work anyways, and maybe it will start to click more. But I don't know where to begin thinking about this.

One way you could write this in JavaScript is perhaps like this:

function sum(root) {
  var result = 1;
  var i = 0;
  var n = root.children.length;
  for (i; i < n; i++) {
    result += sum(root.children[i]);
  }
  return result;
}

How do you write that using mathematical symbols?

Answer 1

The best I can think of is by assuming the tree is rooted (if your tree is unrooted, you can assign a root arbitrarily without changing its structure), and that for each vertex $v$, the set $Ch(v)$ denotes the set of children of $v$. If $v$ is a leaf (a degree one node), then $Ch(v) = \emptyset$.

I guess the assumption of having a root makes sense, since most XML tree files I've seen work with a root, XML having an inherent rooted tree structure.

So if you have that, given a tree $T$ with root $r$, you can write

$$ sum(r) = 1 + \sum_{v \in Ch(r)} sum(v) $$

the idea being that each node counts itself once.

Answer 2

I'm not sure if this is quite what you're looking for, but it seems close.

If you represent the tree structure with a type like a tree = Empty | Node (a, a tree list) (Where a is a type variable) , you can write a sum function like you describe recursively (in some functional pseudocode):

sum Empty = 0
sum Node (_,[]) = 1
sum Node (y,x:xs) = 1 + sum Node(y,xs)

or, more cleanly, but using a bit more machinery:

sum Empty = 0
sum Node (_,l) = fold (+) (map sum l)

Answer 3

From a programming point of view, it is natural to use a recursive function: nodes in a tree = 1 (root)+ sum of nodes in each branch. To count each branch, call it again. You won't do better unless there is a regularity to the tree. For example, if each node except the leaves hs the same number of branches and all the leaves are at the same level, you can sum a geometric series to get there.