question archive A binary tree is ideally weight balanced if, for every node x in the tree, the number of nodes in its two subtrees diers by at most 1
A binary tree is ideally weight balanced if, for every node x in the tree, the number of nodes in its two subtrees diers by at most 1
Subject:Computer SciencePrice: Bought3
A binary tree is ideally weight balanced if, for every node x in the tree, the number of nodes in its
two subtrees diers by at most 1.
1(10 marks) Give an algorithm with worst case running time in O(n) that, given a sorted array
of n elements, constructs an ideally weight balanced binary search tree. Brie
y justify the
correctness of your algorithm and why it runs in O(n) time in the worst case.
2 (10 marks) Give an algorithm which has a worst case running time in O(n) that, given an n
node binary search tree, transforms it into an ideally weight balanced binary search tree for
the same elements. Brie
y justify the correctness of your algorithm and why it runs in O(n)
time in the worst case.
3(5 marks) Prove that there is no O(n) time comparison based algorithm that, given an
unsorted array of n elements, constructs an ideally balanced binary search tree.
