Binary tree

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
    
    # Level-order insertion
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            if not node.left:
                node.left = TreeNode(val)
                return
            if not node.right:
                node.right = TreeNode(val)
                return
            queue.append(node.left)
            queue.append(node.right)
    
    # Traversals
    def inorder(self, root):
        if not root:
            return
        self.inorder(root.left)
        print(root.val, end=' ')
        self.inorder(root.right)
    
    def preorder(self, root):
        if not root:
            return
        print(root.val, end=' ')
        self.preorder(root.left)
        self.preorder(root.right)
    
    def postorder(self, root):
        if not root:
            return
        self.postorder(root.left)
        self.postorder(root.right)
        print(root.val, end=' ')
    
    def level_order(self):
        if not self.root:
            return []
        
        result = []
        queue = [self.root]
        
        while queue:
            level = []
            level_size = len(queue)
            
            for _ in range(level_size):
                node = queue.pop(0)
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level)
        
        return result

class CompleteBinaryTree:
    def __init__(self):
        self.root = None
        self.size = 0
    
    def insert(self, val):
        self.size += 1
        if not self.root:
            self.root = TreeNode(val)
            return
        
        # Convert size to binary and use it as path
        binary = bin(self.size)[3:]  # Skip '0b1'
        node = self.root
        
        for bit in binary[:-1]:
            if bit == '0':
                node = node.left
            else:
                node = node.right
        
        if binary[-1] == '0':
            node.left = TreeNode(val)
        else:
            node.right = TreeNode(val)

class PerfectBinaryTree:
    def __init__(self):
        self.root = None
    
    def build_perfect_tree(self, height):
        def build(level):
            if level == height:
                return None
            node = TreeNode(0)  # Value can be customized
            node.left = build(level + 1)
            node.right = build(level + 1)
            return node
        
        self.root = build(0)

class ThreadedNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.is_threaded = False

class ThreadedBinaryTree:
    def __init__(self):
        self.root = None
    
    def inorder_successor(self, node):
        if not node:
            return None
        
        if node.is_threaded:
            return node.right
        
        node = node.right
        while node and node.left:
            node = node.left
        return node

if not root:
    return None

if not root.left and not root.right:
    return root.val

def is_perfect(self, root):
    level = 0
    current = root
    while current.left:
        level += 1
        current = current.left
    
    return self._is_perfect_recursive(root, level, 0)

def _is_perfect_recursive(self, root, level, current_level):
    if not root:
        return True
    
    if not root.left and not root.right:
        return level == current_level
    
    if not root.left or not root.right:
        return False
    
    return (self._is_perfect_recursive(root.left, level, current_level + 1) and
            self._is_perfect_recursive(root.right, level, current_level + 1))

class CachedNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1
        self.size = 1
        self.depth = 0

class LevelLinkedNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.next = None  # Points to next node in same level

def connect_levels(self, root):
    if not root:
        return
    
    current = root
    while current.left:
        temp = current
        while temp:
            temp.left.next = temp.right
            if temp.next:
                temp.right.next = temp.next.left
            temp = temp.next
        current = current.left

class NodeWithParent:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

def insert_with_parent(self, parent, val):
    node = NodeWithParent(val)
    node.parent = parent
    return node

class NodePool:
    def __init__(self, size=1000):
        self.pool = [TreeNode(0) for _ in range(size)]
        self.available = set(range(size))
    
    def get_node(self, val):
        if self.available:
            idx = self.available.pop()
            node = self.pool[idx]
            node.val = val
            node.left = node.right = None
            return node
        return TreeNode(val)
    
    def return_node(self, node):
        if node in self.pool:
            idx = self.pool.index(node)
            self.available.add(idx)

def clear_tree(self, root):
    if not root:
        return
    
    self.clear_tree(root.left)
    self.clear_tree(root.right)
    
    root.left = None
    root.right = None
    root.val = None

def inorder_iterative(self, root):
    result = []
    stack = []
    current = root
    
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        result.append(current.val)
        current = current.right
    
    return result

def level_order_optimized(self, root):
    if not root:
        return []
    
    result = []
    current_level = [root]
    
    while current_level:
        next_level = []
        values = []
        
        for node in current_level:
            values.append(node.val)
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        
        result.append(values)
        current_level = next_level
    
    return result

# Wrong
def height(self, root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

# Correct (Empty tree height = -1)
def height(self, root):
    if not root:
        return -1
    return 1 + max(self.height(root.left), self.height(root.right))

# Wrong
def delete(self, node):
    if node.left:
        node = node.left
    elif node.right:
        node = node.right
    else:
        node = None

# Correct
def delete(self, node):
    if node.parent:
        if node == node.parent.left:
            node.parent.left = None
        else:
            node.parent.right = None
    node.left = node.right = None

# Wrong (missing level information)
def level_order_wrong(self, root):
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

# Correct (preserves level information)
def level_order_correct(self, root):
    if not root:
        return []
    
    result = []
    queue = [(root, 0)]
    current_level = []
    current_depth = 0
    
    while queue:
        node, depth = queue.pop(0)
        
        if depth > current_depth:
            result.append(current_level)
            current_level = []
            current_depth = depth
        
        current_level.append(node.val)
        
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
    
    result.append(current_level)
    return result