"""Guided lab: rebuild a library's BST catalogue and answer shelf queries."""

from collections import deque
from dataclasses import dataclass


@dataclass
class Node:
    key: int
    left: "Node | None" = None
    right: "Node | None" = None


def insert(root, key):
    """Insert a distinct key without recursion on a potentially skewed tree."""
    if root is None:
        return Node(key)
    current = root
    while True:
        if key == current.key:
            raise ValueError("Book IDs must be distinct")
        side = "left" if key < current.key else "right"
        child = getattr(current, side)
        if child is None:
            setattr(current, side, Node(key))
            return root
        current = child


def inorder(root):
    ordered, stack = [], []
    current = root
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        ordered.append(current.key)
        current = current.right
    return ordered


def levels(root):
    if root is None:
        return []
    queue, result = deque([root]), []
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.key)
            for child in (node.left, node.right):
                if child is not None:
                    queue.append(child)
        result.append(row)
    return result


def balanced_tree(ordered, left=0, right=None):
    """Build actual linked nodes; [left, right) selects the upper middle."""
    if right is None:
        right = len(ordered)
    if left >= right:
        return None
    middle = (left + right) // 2
    return Node(ordered[middle], balanced_tree(ordered, left, middle),
                balanced_tree(ordered, middle + 1, right))


def range_keys(root, low, high):
    """Pruned inorder traversal of inclusive [low, high]."""
    result, stack, current = [], [], root
    while current is not None or stack:
        while current is not None:
            if current.key < low:
                current = current.right
            else:
                stack.append(current)
                current = current.left
        if not stack:
            break
        current = stack.pop()
        if current.key > high:
            break
        result.append(current.key)
        current = current.right
    return result


def kth_key(root, k):
    stack, current = [], root
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.key
        current = current.right
    raise ValueError("k must be between 1 and the number of books")


def lowest_common_ancestor(root, first, second):
    low, high = sorted((first, second))
    while root is not None:
        if high < root.key:
            root = root.left
        elif low > root.key:
            root = root.right
        else:
            return root.key
    raise ValueError("Both book IDs must exist")


def catalogue_report(book_ids, low, high, k, pair):
    """Return answers on the rebuilt tree, plus its before/after height."""
    if not book_ids or low > high or not 1 <= k <= len(book_ids):
        raise ValueError("Nonempty books, low <= high and valid k are required")
    if len(pair) != 2 or any(key not in set(book_ids) for key in pair):
        raise ValueError("Both queried book IDs must exist")
    root = None
    for key in book_ids:
        root = insert(root, key)
    old_height = len(levels(root))
    ordered = inorder(root)
    root = balanced_tree(ordered)
    rows = levels(root)
    return {"ordered": ordered, "height_before": old_height,
            "height_after": len(rows), "levels": rows,
            "in_range": range_keys(root, low, high),
            "kth": kth_key(root, k),
            "lca": lowest_common_ancestor(root, *pair)}