Consider this binary tree (height counts edges):
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
What is the height of the tree?
How many leaves does this tree have?
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
Which statement about this tree is true?
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
Which condition defines a binary search tree (no duplicate keys)?
Which of these trees are valid binary search trees?
(i) 10 (ii) 10 (iii) 10 (iv) 10
/ \ / \ / \ \
5 15 5 15 5 15 20
/ \ / \ / / \ /
2 12 2 7 11 8 20 15
What is the pre-order traversal of this tree?
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
What is the post-order traversal of this tree?
40
/ \
20 60
/ \ / \
10 30 50 70
/ \
25 55
What is the level-order traversal of this tree?
15
/ \
10 25
/ \ / \
5 12 20 30
/ \
11 22
Starting from an empty BST, which insertion order produces exactly this tree?
4
/ \
2 6
/ \ / \
1 3 5 7
The pre-order traversal of a BST is 8 3 1 6 4 7 10 14 13. What is its post-order traversal?
Key 30 is deleted from this BST using the in-order successor for the two-children case. What is the pre-order traversal afterwards?
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
Key 60 is deleted from this BST. What happens?
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
The root 50 is deleted from this BST using the in-order successor. Which key is at the root afterwards?
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
Keys 10 and then 25 are deleted from this BST (in-order successor for the two-children case). What is the pre-order traversal afterwards?
15
/ \
10 25
/ \ / \
5 12 20 30
/ \
11 22
When deleting a node with two children, you copy in its in-order successor. Which statement about that successor is always true?
How do you find the smallest key in a non-empty BST?
The keys 1, 2, 3, 4, 5, 6, 7 are inserted in this order into an empty BST. What is the height of the resulting tree (in edges)?
A BST has n nodes and height h. What is the worst-case cost of contains, insert and delete?
Which traversal is usually implemented with a queue rather than with recursion?
You want to compute each node's height, or release every node of a tree, where each node may be handled only after both of its subtrees have been handled. Which traversal fits?
You save the keys of a BST to a file and later rebuild it by inserting them, in the saved order, into an empty BST. In which traversal order should you save them so that the rebuilt tree has exactly the same shape?
What does this program print?
class Node {
int key; Node left, right;
Node(int key) { this.key = key; }
}
public class Tree {
static Node root;
static void insert(Node node, int key) {
if (node == null) {
node = new Node(key);
return;
}
if (key < node.key) insert(node.left, key);
else insert(node.right, key);
}
static int size(Node n) {
return n == null ? 0 : 1 + size(n.left) + size(n.right);
}
public static void main(String[] args) {
for (int k : new int[] {40, 20, 60}) insert(root, k);
System.out.println(size(root));
}
}
Given the tree below (and the usual Node class), what does mystery(root) return?
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \
35 45 65
static int mystery(Node n) {
if (n == null) return 0;
if (n.left == null && n.right == null) return n.key;
return mystery(n.left) + mystery(n.right);
}
A student checks the BST property with this method. What does it return for the tree shown?
10
/ \
5 15
/ \
2 12
static boolean looksLikeBST(Node n) {
if (n == null) return true;
if (n.left != null && n.left.key >= n.key) return false;
if (n.right != null && n.right.key <= n.key) return false;
return looksLikeBST(n.left) && looksLikeBST(n.right);
}
A BST iterator keeps a stack: it initially pushes the left spine from the root, and each next() pops a node and pushes the left spine of that node's right subtree. For a tree with n nodes and height h, which statement is true?
When deleting a node with two children, the key is replaced by the in-order successor. Explain (a) why the tree is still a BST afterwards and (b) why the successor can always be removed with one of the simple cases (leaf or one child).
A program inserts 100 000 student IDs into a plain BST, reading them from a file that happens to be sorted by ID. Describe the resulting tree, the cost of a lookup, and two ways to avoid the problem.
Describe how a level-order traversal works, why it needs a queue rather than a stack, and how you would modify it to print each level on its own line.
Why is it not enough, when checking whether a binary tree is a BST, to compare each node with its two children? Give a counter-example and describe the correct recursive check, including the bounds passed to each call.
Using the class
class Node {
int key;
Node left, right;
Node(int key) { this.key = key; }
}
write two recursive static methods: int countLeaves(Node n), returning the number of leaves in the tree rooted at n, and int height(Node n), returning its height in edges (−1 for an empty tree, 0 for a single node). Neither method may use a loop or a field.
Write static boolean isBST(Node root) (same Node class as before, int keys, no duplicates allowed) that returns true exactly when the tree satisfies the BST property. Use a recursive helper that receives the bounds as Integer objects, where null means "no bound". It must run in O(n).