Your question is B-Tree Height Coding Problem. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Yahoo Search organizes some in-memory hierarchical structures as balanced multiway trees. Given the root of a B-Tree, write a function that returns its height.
A B-Tree node is represented as a dictionary with a keys list and a children list. A leaf has an empty children list. For this problem, height is measured as the number of levels: an empty tree has height 0, and a tree containing only the root has height 1.
Because a valid B-Tree has all leaves at the same depth, every non-empty child subtree has the same height. You may compute the height by following any child, but your solution should traverse children in a way that remains correct for a valid B-Tree.
Implement height(root), where root is either None or a dictionary of the form {"keys": [...], "children": [...]}. Return an integer representing the tree height. Keys may be any JSON-compatible values and do not affect the result.
Example 1: root = None returns 0 because the tree is empty.
Example 2: A root with two leaf children returns 2, because the tree has a root level and a leaf level.
def height(root):