Binary Search Tree
1. If you are given only the inorder traversal of a binary tree, you can construct the tree uniquely from it.
2. Which of the following sets of traversals can uniquely determine a binary tree?
3. Simulate the insertion of the following numbers into an initially empty binary search tree in order. What is the resulting height of the tree, measured as the number of edges on the longest root-to-leaf path? [1, 2, 3, 4, 5, 6, 7, 8]
4. Simulate the insertion of the following numbers into an initially empty binary search tree in order. What is the resulting height of the tree, measured as the number of edges on the longest root-to-leaf path? [4, 2, 6, 3, 1, 5, 8, 7]
5. Simulate the insertion of the following numbers into an initially empty binary search tree in order. What is the resulting height of the tree, measured as the number of edges on the longest root-to-leaf path? [4, 2, 6, 3, 1, 5, 7, 8]
6. When inserting a new key into a binary search tree, what determines whether the search continues to the left or right child?
7. If the keys 50, 30, 70, 20, and 40 are inserted into an initially empty BST, which node becomes the right child of 30?
8. Consider inserting the keys [8, 3, 10, 1, 6, 14, 4] into an initially empty BST. Which key becomes the left child of 6?
9. Suppose two distinct keys and are inserted into a BST, and . If is inserted before and both eventually become ancestors/descendants of one another, which node can be the ancestor?