In a tree containing n nodes, how much time does it take to find the parent of a

Question

In a tree containing n nodes, how much time does it take to find the parent of a given node in the worst case? Does your answer change if you know that a node of the tree can never have more than k children?

Problem 5.10. At the cost of one extra bit of storage in records of type treenodel, we can make it possible to find the parent of any given node. The idea is to use the next-sibling field of the rightmost member of a set of siblings to point to their common parent. Give the details of this approach. In a tree containing n nodes, how much time does it take to find the parent of a given node in the worst case? Does your answer change if you know that a node of the tree can never have more than k children?

Explanation / Answer

It's constant. At a point of time, for a given node in a tree, it's takes constant time irrespective of no of child nodes.

So, answer won't even if we know that tree can never have more than k children.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.