Binary Trees and Binary Search Trees Questions

# O(n) detection of degenerate binary tree
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val; self.left = left; self.right = right

def is_degenerate(root):
    if not root: 
        return True
    stack = [root]
    while stack:
        node = stack.pop()
        # if node has two children, not degenerate
        if node.left and node.right:
            return False
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return True

import json, struct, hashlib, time
from typing import Optional, List, Tuple

MAGIC = b'BSTSNAP\x00'  # 8 bytes
HEADER_FMT = '!I'       # 4-byte header length

class Node:
    def __init__(self, v:int, left=None, right=None):
        self.v = v; self.left = left; self.right = right

def _serialize_tree_preorder(root:Optional[Node]) -> List[int]:
    # Use sentinel None as marker
    out=[]
    def dfs(n):
        if n is None:
            out.append(None); return
        out.append(n.v)
        dfs(n.left); dfs(n.right)
    dfs(root); return out

def write_snapshot(root:Optional[Node], version: Tuple[int,int], path:str):
    payload = json.dumps(_serialize_tree_preorder(root), separators=(',',':')).encode()
    header = {
        'version': f'{version[0]}.{version[1]}',
        'ts': int(time.time()),
        'nodes': payload.count(b',')+1 if payload else 0
    }
    header_bytes = json.dumps(header, separators=(',',':')).encode()
    hdr_len = struct.pack(HEADER_FMT, len(header_bytes))
    core = MAGIC + hdr_len + header_bytes + payload
    checksum = hashlib.sha256(core).digest()
    with open(path,'wb') as f:
        f.write(core + checksum)

def _parse_version(s:str) -> Tuple[int,int]:
    a,b = s.split('.'); return int(a), int(b)

def upgrade_payload(old_payload:bytes, old_version:Tuple[int,int], cur_version:Tuple[int,int]) -> bytes:
    # Example upgrade: no-op or transformation code per version
    # For demo, assume backward-compatible changes handled here
    return old_payload

def read_snapshot(path:str, cur_version:Tuple[int,int]) -> Optional[Node]:
    with open(path,'rb') as f:
        data = f.read()
    if len(data) < len(MAGIC)+4+32: raise ValueError('corrupt/too small')
    if not data.startswith(MAGIC): raise ValueError('bad magic')
    idx = len(MAGIC)
    hdr_len = struct.unpack(HEADER_FMT, data[idx:idx+4])[0]; idx+=4
    header_bytes = data[idx:idx+hdr_len]; idx+=hdr_len
    # remaining: payload + checksum
    checksum = data[-32:]; payload = data[idx:-32]
    core = data[:len(data)-32]
    if hashlib.sha256(core).digest() != checksum: raise ValueError('checksum mismatch')
    header = json.loads(header_bytes.decode())
    file_version = _parse_version(header['version'])
    if file_version == cur_version:
        pass
    elif file_version < cur_version:
        payload = upgrade_payload(payload, file_version, cur_version)
    else:
        # newer file: if minor compatible (same major) accept, else reject
        if file_version[0] > cur_version[0]:
            raise ValueError('snapshot from newer incompatible major version')
    # rebuild tree
    arr = json.loads(payload.decode())
    it = iter(arr)
    def build():
        try:
            v = next(it)
        except StopIteration:
            return None
        if v is None: return None
        node = Node(v)
        node.left = build(); node.right = build()
        return node
    return build()