Data Structure I Practice Test 6

1. Which of the following tree traversals work if the null left pointer pointing to the predecessor and null right pointer pointing to the successor in a binary tree?

2. Why the below pseudo code where x is a value, wt is weight factor and t is root node can't insert?

WeightBalanceTreeNode insert(int x, int wt, WeightBalanceTreeNode k) :
       
           if (k == null)
                k = new WeightBalanceTreeNode(x, wt, null, null)
           else if (x < t.element) :
            
                k.left = insert (x, wt, k.left)
                if (k.left.weight < k.weight)
                    k = rotateWithRightChild (k)
            
            else if (x > t.element) :
            
                k.right = insert (x, wt, k.right)
                if (k.right.weight < k.weight)
                    k = rotateWithLeftChild (k)
 

3. Which of the following is true?

4. What does the below definations convey?
i. A binary tree is balanced if for every node it is gonna hold that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
ii. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

5. Which of the following is false?

6. Which node is the child node of Node D in the following ternary tree?

7. Is it true that splay trees have O(logn) amortized complexity ?

8. Which of the dynamic operations are used in Top Tree data structure implementation?

9. Which of the following is false?

10. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?