4. Summing up values stored in binary tree. CountBTR is a recursive algorithm fo

Question

4. Summing up values stored in binary tree. CountBTR is a recursive algorithm for counting the nodes in a binary tree, see lecture notes. Modify the algorithm to compute the sum of all the numbers stored in a binary tree T, which stores a number at each node. Hint: a node doesn’t count as 1 anymore, but rather as V, where V is the number it stores.
a. Give a brief step by step description of the algorithm.
b. Give a pseudocode description of the algorithm.

c. What is the algorithm running time, assuming that the binary tree stores n nodes? Explain.


If you know any of those a or b or c. Please help me :) Thank you.

Explanation / Answer

for traversing the binary tree and summing up value, you need to traverse the tree. One of the many tree traversal algorithms is known as BFS or breadth first traversal. The pseudo-code is below - 1) Enqueue the root node 2) Dequeue a node and examine it If the element sought is found in this node, quit the search and return a result. Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered. 3) If the queue is empty, every node on the graph has been examined – quit the search and return "not found". 4) If the queue is not empty, repeat from Step 2. Pseudo code 1 procedure BFS(G,v): 2 create a queue Q 3 enqueue v onto Q 4 mark v 5 while Q is not empty: 6 t ? Q.dequeue() 7 if t is what we are looking for: 8 return t 9 for all edges e in G.incidentEdges(t) do 10 o ? G.opposite(t,e) 11 if o is not marked: 12 mark o 13 enqueue o onto Q Please see the images below to understand better RUNNING TIME The time complexity can be expressed as O( | E | + | V | ) since every vertex and every edge will be explored in the worst case. ( E-> edges, V-> vertex)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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