views:

110

answers:

2

Can you guys help me with the algorithm to do these things? I have preorder, inorder, and postorder implemented, and I am given the hint to traverse the tree with one of these orders. I am using dotty to label (or "visit") the nodes.

Depth is the number of edges from the root to the bottom leaf, so everytime I move, I add +1 to the depth? Something like that?

No idea about the algorithm for descendants. They are asking about the number of nodes a specific node has under itself.

These are normal trees btw.

+1  A: 
depth(tree) = 1+ max(depth(tree.left), depth(tree.right));

descendants(tree) = descendants(tree.left) + descendants(tree.right);

For either, returning 0 for a null pointer would end the recursion.

Jerry Coffin
`descendants` will always return 0.
Potatoswatter
@Potatoswatter:yes, since it looked like homework, I deliberately left a few things for him to figure out on his own...
Jerry Coffin
+2  A: 

Is this a question for homework? If so, please tag this question with the homework tag so that it is clear. My answer assumes it is for homework.

Trees are a recursive data structure, so the algorithms that operate on them will often be recursive. Recursive algorithms need a base case and an inductive case. For trees, the base case will be what you do when you are visiting a leaf node (i.e. a node without children). The inductive case will be what you do when you are visiting an internal node (i.e. a node with at least one child).

For calculating depth (or "height" of the tree):

  • Base case: What is the depth of a node without children?
  • Inductive case: Given that you have the depths of all of your children (which could be different), what is the depth of the current node you're visiting?

For calculating descendant count:

  • Base case: How many descendants does a node without children have?
  • Inductive case: Given that you know the descendant count of all of your children, what is the descendant count of the current node you're visiting?

I encourage you to ask clarifying questions.

Chris Schmich