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):