BST/Bash/GIT
git pull reports a merge conflict, what must you do before pushing?
Resolve the conflict markers in the file, git add it, and git commit to finish the merge. Then git push.
The red property says a red node’s children must be this color.
Black
In a valid B-tree, the path from the root to the leftmost leaf has 12 nodes. This is how many nodes the path to any other leaf has.
Exactly 12
This Bash command prints the contents of answers.txt to the terminal
cat answers.txt
JUnit 5 sees a class with four methods. The first is @Test public boolean randomInsertTest(). The second has no @Test annotation. The third is @Test public void heightTest1(). The fourth is @Test public static void heightTest2(). How many tests does it run?
1 test. randomInsertTest doesn’t return void, the second has no @Test, and the static one is invalid.
A BST is built by inserting 8, 3, 10, 1, 6, 14, 4 in that order. Give its post-order traversal.
1, 4, 6, 3, 14, 10, 8. The tree is 8(3(1, 6(4)), 10(null, 14))
A tree has black-or-red root 6 with two leaf children, 3 and 9. Must 3 and 9 be the same color? Explain
Yes. Both are leaves, so each leads to null children. If one were red and the other black, the paths through them would have different black counts, which breaks the black-height property.
A 2-3-4 tree with three levels can hold at most this many nodes
21 nodes (1 + 4 + 16)
Runnable has the method public void run();. Which of these is a valid lambda for it: (x) -> System.out.println(x), () -> 3 + 3, or () -> System.out.println("hi")
() -> System.out.println("hi"). The first takes a parameter, and 3 + 3 isn’t a valid statement for a void method
The project 1 iterator stores a stack of nodes on the path to the next value. What is its worst-case space complexity for a Red-Black Tree with N nodes, and why?
O(log N). The stack holds one root-to-node path, and an RBT’s height is at most about 2·log N
Tests.java and its dependencies are in your working directory, and junit5.jar is one directory up. Write the full command to compile it.
javac -cp ../junit5.jar:. Tests.java. -cp sets the classpath, and :. lets javac find the other classes in the working directory. -jar is for running jars, and java runs code rather than compiling it
Insert 1, 2, 3 into an empty RBT using the lecture algorithm. Give the final root and the color of every node.
The root is 2 (black), and 1 and 3 are both red. Node 2 is red under 1 and 3 is red under 2, and the aunt is null. So 2 and 1 are rotated, then recolored.
With pre-emptive splitting, a 2-3-4 tree grows taller only when this node splits
The root
git log shows three commits: b68f9c3 (HEAD → dev, “Removing answers”), 46f0da4 (“Adding midterm answers”), and c8e11af (main, “Adding midterm questions”). You want a branch final at the “answers” commit. What command do you run right before git branch final
git checkout 46f0da4 (the full hash also works). This detaches HEAD at that commit, so git branch final creates the branch there
Write an iterative contains(T lookup) for a BST. You may use isEqual(lookup, node), lookupIsGreater(lookup, node), getLeft() and getRight()
while (currentNode != null) {
if (isEqual(lookup, currentNode)) return true;
if (lookupIsGreater(lookup, currentNode))
currentNode = currentNode.getRight();
else
currentNode = currentNode.getLeft();
}
return false;In an AVL tree, every node’s balance factor must fall in this range. A node whose right child is left-heavy needs this fix.
The range is -1, 0, or +1, meaning subtree heights differ by at most 1. The right-left case needs a right rotation on the right child, then a left rotation on the node.
In a valid RBT, node 5 has only a right child, 6, and no left child. What color must 6 be, and why?
Red. Node 5’s missing left child is a null path, so 6 can’t add an extra black to the right side.
Insert 5, 10, 15, 20, 25, 30 in order into an empty 2-3-4 tree using pre-emptive splits. Give the final tree
Root [10 20] with leaves [5], [15], and [25 30]. The root splits on the insert of 20, and [15 20 25] splits on the insert of 30
True or False: your teammate pushes to a branch, and you immediately run git push to that same branch with a new local commit. Your push succeeds
False. The push is rejected (non-fast-forward) because the remote has a commit you don’t have. You need to git pull or fetch and merge first
In an AVL tree, grandParent is imbalanced and its left child, parent, has its left child, child (the left-left case). Write the three lines that complete the rotation. Node has public leftChild and rightChild, and grandParent is the root of this subtree’s parent link.
This is a right rotation, and the order matters
parent.leftChild = child.rightChild;
The rotation lifts child over parent: parent.leftChild = child.rightChild; child.rightChild = parent; grandParent.leftChild = child;
Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree. Give the final root, the shape of the tree, and the last rebalancing operation performed.
The root is 30. The tree is 30(20(10, 25), 40(null, 50)). Inserting 30 and 50 each cause a single left rotation, and inserting 25 causes a right-left double rotation at 20.
Insert 11 into this tree: 15(B) has left child 5(R) and right child 19(B). Node 5 has children 4(B) and 12(B), and 12 has children 10(R) and 14(R). Name the node 11 is inserted below, the first three nodes recolored, the first two nodes rotated, and the final number of red nodes.
Node 11 goes below 10. The first recolors are 10 and 14 → black, then 12 → red. The first rotations are 12 over 5, then 12 over 15, and 12 ends up black. The final tree is 12(5(4, 10(,11)), 15(14, 19)), with 3 red nodes (5, 15, 11).
A 2-3-4 tree has root [4 12] and leaves [1 2 3], [6 8 10], [13 14 15]. Inserting an integer x (not already in the tree) produces a 4-node [4 8 12]. How many possible values of x are there?
x = 5, 7, 9, 11. These land in the middle leaf [6 8 10], which is full, so it splits and 8 moves up. Landing in [1 2 3] gives [2 4 12], and landing in [13 14 15] gives [4 12 14]
This code runs: List<Object> list = new ArrayList<>(); for (int i = 0; i < 3; i++) { final int j = i * i; Program p = () -> System.out.println("Hello " + j); list.add(p); }, where Program has void derez(). How many Program objects exist, and what final line prints “Hello 4”
Program objects exist (capturing j = 0, 1, 4). The line is ((Program) list.get(2)).derez();. The cast is needed because the list holds Object
Complete the red-aunt branch of ensureRedProperty(BinaryNode<T> newRedNode). The parent is red and aunt is red and non-null. You have getParent(), isBlackNode, and recursion available
newRedNode.getParent().isBlackNode = true; aunt.isBlackNode = true; BinaryNode<T> grandparent = newRedNode.getParent().getParent(); grandparent.isBlackNode = false; ensureRedProperty(grandparent);