Assume that you have a complete tree with 200 nodes, and that you represent it i
ID: 3721106 • Letter: A
Question
Assume that you have a complete tree with 200 nodes, and that you represent it in array form.
Node A of the tree is in position 50 of the array. What are the indices of A’s left child, right child, and parent? Explain how you got your answers.
What is the height of the tree? Explain your answer briefly.
The bottom level of the tree contains some number of leaf nodes. Is the rightmost leaf node in the bottom level the left child of its parent or the right child of its parent? Explain your answer briefly.
In Problem 6, you will implement a method that determines if the complete tree corresponding to an array of values is a heap. What is the efficiency of determining if an array of length n represents a heap in the best case? In the worst case? Use big-O notation, and explain your answers briefly.
Explanation / Answer
Answering your first 4 questions, as it is not possible to answer all of your questions in one thread:
Assume that you have a complete tree with 200 nodes, and that you represent it in array form.
=> The Tree is arranged in array level by level.. so first 1 element from level 1 is put, then 2 elements from level2 are put, then 4 elements from level3 are put and so on..
=> If any element is not present, then it is left blank and is not filled.
Node A of the tree is in position 50 of the array. What are the indices of A’s left child, right child, and parent? Explain how you got your answers.
=> Any node at index i in array, has its left child present on index 2*i + 1 and right child on index 2*i + 2.
=> So node at index 50, will have its left child at 101, and right child at index 102.
=> To get the index of parent of node at index i, we can do [(i+1)/2], where [] represents the floor function to get nearest integer
=> So node at index 50, has its parent present on [51/2] = index 25
What is the height of the tree? Explain your answer briefly.
=> Any tree of height h, will have 2^h - 1 nodes in total..
=> so 50 = 2^h - 1
=> h = log(51) on base 2 = 5.67, but height being the complete number will be next larger whole number, i.e. 6. Hence height is 6.
The bottom level of the tree contains some number of leaf nodes. Is the rightmost leaf node in the bottom level the left child of its parent or the right child of its parent? Explain your answer briefly.
=> If you see, the left node of index i is at 2*i + 1, while right child at 2*i + 2.
=> So if for node at index x, you want to know if it is right or left child of your parent, then check if the index is even or odd.
=> if index x is even, then it is a right child of its parent.
=> if index x is odd, then it is a left child of its parent.