"""
LC 108 — Convert Sorted Array to Binary Search Tree.

Three implementations of the array → BST construction:
    1. sorted_array_to_bst            — half-open [lo, hi) recursive (canonical, recommended).
    2. sorted_array_to_bst_inclusive  — [lo, hi] inclusive recursive (also correct).
    3. sorted_array_to_bst_iterative  — explicit-stack iterative form.

Plus LC 109 follow-up (sorted singly-linked list → BST):
    sorted_list_to_bst — inorder pointer trick, O(N) time, O(log N) stack, O(1) extra.

INVARIANT (input): nums is strictly ascending sorted.
INVARIANT (output): result is a height-balanced BST whose inorder == nums.
"""

from __future__ import annotations

import math
import random
import sys
from typing import Optional

sys.setrecursionlimit(20_000)


class TreeNode:
    __slots__ = ("val", "left", "right")

    def __init__(self, val: int = 0, left: Optional["TreeNode"] = None,
                 right: Optional["TreeNode"] = None):
        self.val = val
        self.left = left
        self.right = right


class ListNode:
    __slots__ = ("val", "next")

    def __init__(self, val: int = 0, nxt: Optional["ListNode"] = None):
        self.val = val
        self.next = nxt


# ----------------------------------------------------------------------
# Solution A — half-open [lo, hi) recursive (canonical).
# ----------------------------------------------------------------------

def sorted_array_to_bst(nums: list[int]) -> Optional[TreeNode]:
    def build(lo: int, hi: int) -> Optional[TreeNode]:
        # INVARIANT: nums[lo:hi] is the inorder sequence of the subtree we are about to build.
        if lo >= hi:
            return None
        mid = (lo + hi) // 2
        return TreeNode(nums[mid], build(lo, mid), build(mid + 1, hi))

    return build(0, len(nums))


# ----------------------------------------------------------------------
# Solution B — [lo, hi] inclusive recursive (variant).
# ----------------------------------------------------------------------

def sorted_array_to_bst_inclusive(nums: list[int]) -> Optional[TreeNode]:
    def build(lo: int, hi: int) -> Optional[TreeNode]:
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        return TreeNode(nums[mid], build(lo, mid - 1), build(mid + 1, hi))

    return build(0, len(nums) - 1)


# ----------------------------------------------------------------------
# Solution C — explicit-stack iterative (no recursion).
# ----------------------------------------------------------------------

def sorted_array_to_bst_iterative(nums: list[int]) -> Optional[TreeNode]:
    if not nums:
        return None
    n = len(nums)
    # Build root first to anchor the parent-pointer logic.
    root_mid = (0 + n) // 2
    root = TreeNode(nums[root_mid])
    # Stack of (parent_node, child_side, lo, hi)  — half-open.
    stack: list[tuple[TreeNode, str, int, int]] = [
        (root, "L", 0, root_mid),
        (root, "R", root_mid + 1, n),
    ]
    while stack:
        parent, side, lo, hi = stack.pop()
        if lo >= hi:
            continue
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])
        if side == "L":
            parent.left = node
        else:
            parent.right = node
        stack.append((node, "L", lo, mid))
        stack.append((node, "R", mid + 1, hi))
    return root


# ----------------------------------------------------------------------
# LC 109 follow-up — sorted linked list → BST via inorder pointer.
# ----------------------------------------------------------------------

def sorted_list_to_bst(head: Optional[ListNode]) -> Optional[TreeNode]:
    # Count length once.
    n = 0
    cur = head
    while cur is not None:
        n += 1
        cur = cur.next

    # Mutable "current" pointer captured in closure.
    ptr: list[Optional[ListNode]] = [head]

    def build(size: int) -> Optional[TreeNode]:
        if size <= 0:
            return None
        left_size = size // 2
        left = build(left_size)
        # ptr[0] now points at the value that becomes this node.
        node = TreeNode(ptr[0].val)  # type: ignore[union-attr]
        ptr[0] = ptr[0].next  # type: ignore[union-attr]
        right = build(size - left_size - 1)
        node.left = left
        node.right = right
        return node

    return build(n)


# ----------------------------------------------------------------------
# Validation helpers.
# ----------------------------------------------------------------------

def inorder_values(root: Optional[TreeNode]) -> list[int]:
    out: list[int] = []
    stack: list[TreeNode] = []
    cur = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        node = stack.pop()
        out.append(node.val)
        cur = node.right
    return out


def is_valid_bst(root: Optional[TreeNode]) -> bool:
    prev: Optional[int] = None
    stack: list[TreeNode] = []
    cur = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        node = stack.pop()
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        cur = node.right
    return True


def height(root: Optional[TreeNode]) -> int:
    """Edge-count height; height(None) = -1, height(leaf) = 0."""
    if root is None:
        return -1
    return 1 + max(height(root.left), height(root.right))


def is_height_balanced(root: Optional[TreeNode]) -> bool:
    """Returns True iff |h(left) - h(right)| <= 1 at every node. O(N) via post-order."""
    ok = True

    def go(node: Optional[TreeNode]) -> int:
        nonlocal ok
        if node is None or not ok:
            return -1
        lh = go(node.left)
        rh = go(node.right)
        if abs(lh - rh) > 1:
            ok = False
        return 1 + max(lh, rh)

    go(root)
    return ok


def list_from(vals: list[int]) -> Optional[ListNode]:
    head: Optional[ListNode] = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head


# ----------------------------------------------------------------------
# Stress test.
# ----------------------------------------------------------------------

def stress_test() -> None:
    rng = random.Random(42)
    n_iter = 1000
    expected_max_h = lambda n: math.ceil(math.log2(n + 1)) if n > 0 else -1

    for _ in range(n_iter):
        size = rng.randint(0, 100)
        # Build strictly-ascending nums.
        nums = sorted(rng.sample(range(-10_000, 10_000), size))

        for build_fn in (sorted_array_to_bst, sorted_array_to_bst_inclusive, sorted_array_to_bst_iterative):
            root = build_fn(nums)
            assert inorder_values(root) == nums, f"{build_fn.__name__}: inorder != nums"
            assert is_valid_bst(root), f"{build_fn.__name__}: not a valid BST"
            assert is_height_balanced(root), f"{build_fn.__name__}: not height-balanced"
            # Verify optimal height bound.
            h = height(root)
            assert h <= expected_max_h(size), (
                f"{build_fn.__name__}: height {h} exceeds optimal {expected_max_h(size)} for n={size}"
            )

        # LC 109 cross-check.
        head = list_from(nums)
        tree_from_list = sorted_list_to_bst(head)
        assert inorder_values(tree_from_list) == nums, "sorted_list_to_bst: inorder != nums"
        assert is_valid_bst(tree_from_list), "sorted_list_to_bst: not a valid BST"
        assert is_height_balanced(tree_from_list), "sorted_list_to_bst: not height-balanced"

    print(f"stress_test: {n_iter} sorted arrays — all 3 array builds + LC 109 produce valid, balanced, inorder-matching BSTs.")


# ----------------------------------------------------------------------
# Edge cases.
# ----------------------------------------------------------------------

def edge_cases() -> None:
    # Empty.
    for fn in (sorted_array_to_bst, sorted_array_to_bst_inclusive, sorted_array_to_bst_iterative):
        assert fn([]) is None
    assert sorted_list_to_bst(None) is None

    # Single.
    for fn in (sorted_array_to_bst, sorted_array_to_bst_inclusive, sorted_array_to_bst_iterative):
        r = fn([7])
        assert r is not None and r.val == 7 and r.left is None and r.right is None

    # Two elements: both midpoint conventions are valid.
    r1 = sorted_array_to_bst([1, 2])
    assert inorder_values(r1) == [1, 2]
    assert is_valid_bst(r1) and is_height_balanced(r1)

    # Perfect 7: root must be 4.
    r7 = sorted_array_to_bst([1, 2, 3, 4, 5, 6, 7])
    assert r7 is not None and r7.val == 4
    assert inorder_values(r7) == [1, 2, 3, 4, 5, 6, 7]
    assert height(r7) == 2  # log2(8) - 1

    # Canonical LC example.
    r_canon = sorted_array_to_bst([-10, -3, 0, 5, 9])
    assert inorder_values(r_canon) == [-10, -3, 0, 5, 9]
    assert is_valid_bst(r_canon) and is_height_balanced(r_canon)

    # 1000-elem (verify no stack overflow at log_2(1001) ≈ 10 depth).
    big = list(range(1000))
    r_big = sorted_array_to_bst(big)
    assert inorder_values(r_big) == big
    assert is_height_balanced(r_big)
    assert height(r_big) <= math.ceil(math.log2(1001))

    # LC 109 single + canonical.
    one = list_from([42])
    r_one = sorted_list_to_bst(one)
    assert r_one is not None and r_one.val == 42

    canon_list = list_from([-10, -3, 0, 5, 9])
    r_lc = sorted_list_to_bst(canon_list)
    assert inorder_values(r_lc) == [-10, -3, 0, 5, 9]
    assert is_height_balanced(r_lc)

    print("edge_cases: PASS")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")