CODEWITHSUNDEEP
algorithmdata-structuresrecursionbinary-treedivide-and-conquer
Abhijith Madhav
Abhijith Madhav

Reputation: 2818

What is the implication of recursive calls modeling a perfect binary tree?

I'm learning data-structures and algorithms. The book I refer to(Sedgwick) uses 'finding the maximum element' to illustrate the divide-and-conquer strategy. This algorithm divides an array midway into two parts, finds the maximum elements in the two parts (recursively), and returns the larger of the two as the maximum element of the whole array.

The below is an exercise question asked

Modify the divide-and-conquer program for finding the maximum element in an array (Program 5.6) to divide an array of size N into one part of size k = 2^(lg N – 1) and another of size, N – k (so that the size of at least one of the parts is a power of 2).

Draw the tree corresponding to the recursive calls that your program makes when the array size is 11, similar to the one shown for Program 5.6.

I see that the left sub-tree of such a binary tree is a perfect binary tree because the size of the first subset is a power of two. What is the implication the author is hoping that I should get from this?

Upvotes: 4

Views: 282

Answers (1)

mitchus
mitchus

Reputation: 4877

I suppose that one nugget of this exercise lies in the k. It makes the point that if you use this formula for k in a binary recursion, then your underlying tree is "pretty", in the sense that the left subtree of every node (not just the root) is a perfect binary tree.

Of course it is also well-behaved in the "ideal" case when N is a power of 2; k is then simply N/2, and every subtree (not only the left) is a perfect binary tree.

Upvotes: 1

Related Questions