Search code examples
c++treedepth

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.

Solution 
  • 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.