Data-structures Exercises

Practice Questions — Complexity analysis, BST

Complexity analysis:

1. Compare merge sort algorithms with various partitioning options.

2. Write down the lower bound, upper bound and order functions for f(n) = 0.5 n^3 + 2 n^2 + log n

Binary Search Trees:

1. Given an inorder traversal and a postorder traversal, write an algorithm to reconstruct the tree.

2. Find the nearest match of a given value in a binary search tree.

3. Write a function to check whether two BSTs are structurally identical.

4. Write a function to find the size of a BST.

5. Write a function to compute the sum of all elements in a BST.