Suppose we are given a perfectly balanced binary tree T (a perfectly balanced binary tree is...

Transcribed Image Text:

Suppose we are given a perfectly balanced binary tree T (a perfectly balanced binary tree is one in which every non-leaf has exactly two children, and every leaf is located at the same depth of the tree as every other leaf) in which every node is assigned a number. Give a divide and conquer algorithm which will rearrange the leaf nodes such that: • The overall shape of the tree remains the same. • The numbers associated with the leaf nodes appear in increasing sorted order from left to right. • The number associated with every parent node is the sum of its two children. Provide a runtime analysis of your algorithm. As an example, the tree on the left would be rearranged to look like the tree on the right: 4 5 10 1 3 5 2 1 3 2 10 3 7 4 Suppose we are given a perfectly balanced binary tree T (a perfectly balanced binary tree is one in which every non-leaf has exactly two children, and every leaf is located at the same depth of the tree as every other leaf) in which every node is assigned a number. Give a divide and conquer algorithm which will rearrange the leaf nodes such that: • The overall shape of the tree remains the same. • The numbers associated with the leaf nodes appear in increasing sorted order from left to right. • The number associated with every parent node is the sum of its two children. Provide a runtime analysis of your algorithm. As an example, the tree on the left would be rearranged to look like the tree on the right: 4 5 10 1 3 5 2 1 3 2 10 3 7 4

Answer rating: 100% (QA)

o achieve the rearrangement of the leaf nodes in a perfectly balanced binary tree while maintaining the overall shape and satisfying the sum property ... View the full answer