Algorithms: Given the balanced binary trees T_1 and T_2, which contain m and n e

Question

Algorithms:

Given the balanced binary trees T_1 and T_2, which contain m and n elements repectively, we want to determine whether they have some particular key in common. Assume an advesarial sequence that placed m and n items into the two trees.

(a) Suppose our algorithm traverses each node of T_1 using an in-order traversal and if the key corresponding to the current node traversed exists in T_2. Express the asymptotic running time of this procedure, in terms of m and n.

Please give descriptive answer to the problem so I can understand. Thank you.

Part B is located on another post.

Explanation / Answer

Given that the two trees are balanced binary trees. Since they are binary trees and not binary search tree, we have to look for all the nodes.

For an in-order traversal of T_1, it takes O(m) time.

Similarly, in-order traversal of T_2, it takes O(n) time.

Since we are performing an in-order traversal of T_2 for each and every node in T_1, the in-order traversal of T_2 is repeated m times.

Hence, the overall complexity is O(m*n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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