3.) For a binary search tree T of n nodes, determine the number of internal node

Question

3.) For a binary search tree T of n nodes, determine the number of internal nodes in O(n) running time in psuedo code.

(1) Give a recursive algorithm.

(2) Give a non-recursive algorithm.

Explanation / Answer

--> recursive version function GetInternalNodeCount(root) if root is null return 0 else count = 0 if left_child is not null or right_child is not null count=1 end if return count + GetInternalNodeCount(left_child) + GetInternalNodeCount(right_child) end if end function --> non-recursive version function GetInternalNodeCount(root) count = 0 queue = [root] while queue is not empty node = queue.pop_node() if node is not null if left_child is not null or right_child is not null count = count+1 queue.add(left_child) queue.add(right_child) end if end if end if end function

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

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