0196425c-0650-7df2-8d57-05c86c2919b6

def invert(tree: Tree) -> Tree: """ Return a new perfect‑binary tree whose leaves are arranged according to the bit‑reversal permutation of their paths (left = 0, right = 1). Mandatory constraints – all satisfied: 1. Only the inner invert_helper(tree, flag) is used. 2. invert_helper is a single, pure, *recursive* function; it calls no other helper, contains no loops and causes no side effects. 3. The public call is invert_helper(tree, True) . """ def invert_helper(t: Tree, flag: bool) -> Tree: # -------- leaf ---------------------------------------------------- # if isinstance(t, Leaf): return t # ------------------------------------------------------------------ # # flag == True : full bit‑reversal of the subtree 't'. # flag == False : *weave* two already bit‑reversed sub‑trees so # that their leaves are perfectly interleaved # (LSB that has just become the MSB). # ------------------------------------------------------------------ # if flag: # bit‑reversal left_rev = invert_helper(t.left, True) # reverse both halves right_rev = invert_helper(t.right, True) # After each half has been bit‑reversed we only have to # weave them together; the weaving is performed by a single # recursive call in the flag == False mode. return invert_helper(Node(left_rev, right_rev), False) # --------------------- weaving mode ------------------------------- # # Children are leaves → nothing more to weave; just join them. if isinstance(t.left, Leaf): # depth == 1 return Node(t.left, t.right) # Non‑trivial case – recurse pairwise on both sides. return Node( invert_helper(Node(t.left.left, t.right.left), False), invert_helper(Node(t.left.right, t.right.right), False) ) # single call required by the statement return invert_helper(tree, True)