CODEWITHSUNDEEP
c++treedepth
yuudachi
yuudachi

Reputation: 2346

Calculating depth and descendants of tree

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.

Upvotes: 1

Views: 3359

Answers (2)

Chris Schmich
Chris Schmich

Reputation: 29466

Is this a question for homework? 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.

Upvotes: 5

Jerry Coffin
Jerry Coffin

Reputation: 490088

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.

Upvotes: 1

Related Questions