# Homework Help: Program that counts all the vertices in a given tree

1. Jun 29, 2013

### snickersnee

1. The problem statement, all variables and given/known data

"Write a program that counts all the vertices in a given tree."

Any language can be used. (I've been using Perl mostly but could do C too. C++ would be ok too, if it was significantly easier.)

2. Relevant equations

I've been trying to find this. I read if a tree has n levels, the number of vertices is 2^{n-1}. And for n edges, the vertices are (n-1). Maybe that will help.

3. The attempt at a solution

I'm not making much progress because I don't even know what the input is supposed to look like. Also, this seems like the kind of thing that there's a formula for.
-What does the input look like? (how is the tree entered into the program?) I've seen the graphical version. But how would that tree be typed in?

I'm a grad student in electrical engineering but software is not my area of specialization. I didn't take the algorithms class. The problem would probably be simple to anyone who had taken the class. If you know a good reference book or website, I'd appreciate that too. Googling hasn't helped much.

2. Jun 30, 2013

### Joffan

This process is usually called a traversal of the tree, visiting each node, using the self-similar nature of trees - each branch is treated as a tree. The routine should accept a pointer to the root node which will have pointers to other parts of the tree. See Binary Tree (Wiki). A typical traversal can be some variation of:
- process left pointer if not null
- act on current node
- process right pointer if not null