Answer Happy

Why can't the tree you just constructed be colored to form a legal red-black tree? A. It actually can be colored to form a legal red-black tree if we make the shallowest leaf node double black. B. A binary search tree cannot be a red-black tree. C. Path from root to deepest node is more than twice the length of the path from root to shallowest node, so it is impossible to have equal black height even if we make as many nodes red as is allowed D. Red-black trees are balanced, and this tree is not balanced as there are leaves at different depths. A single rotation on the BST in the previous question can transform it into a BST that can be colored as a red-black tree. After this rotation, the root node is (fill in the key).