(a) The worst case time complexity of counting the number of children of an inte

Question

(a) The worst case time complexity of counting the number of children of an internal node on a tree (general tree) is O(n). True or False

(b) The worst case time complexity of removing an external(leaf) node referenced by variable p on a binary tree is O(n). True or False

(c) Assume prefers to a node on a binary tree. The node structure is defined as an element field and three reference variables as shown on the slides. The worst time complexity of updating the element field of p's parent is O(n). True or False

(d) The time complexity to determine whether a node is an internal or external node on a reference-based implementation binary tree is O(1). True or False

Explanation / Answer

(a) The worst case time complexity of counting the number of children of an internal node on a tree (general tree) is O(n).

True

(b) The worst case time complexity of removing an external(leaf) node referenced by variable p on a binary tree is O(n).

False

(c) Assume prefers to a node on a binary tree. The node structure is defined as an element field and three reference variables as shown on the slides. The worst time complexity of updating the element field of p's parent is O(n).

False

(d) The time complexity to determine whether a node is an internal or external node on a reference-based implementation binary tree is O(1).

True

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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