590. N-ary Tree Postorder Traversal

Approach: Right-to-left, then root-to-left. Use a stack with a visited set to track processed nodes.

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

def postorder(root):
    if not root:
        return []
    stack = [root]
    result = []
    visited = set()
    while stack:
        current = stack[-1]
        if not current.children or current in visited:
            result.append(current.val)
            stack.pop()
            continue
        for child in reversed(current.children):
            stack.append(child)
        visited.add(current)
    return result

105. Construct Binary Tree from Preorder and Inorder Traversal

Approach: Preorder provides root order (root-left-right). Inorder splits left/right subtrees at root position.

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

def buildTree(preorder, inorder):
    position = {val: idx for idx, val in enumerate(inorder)}
    
    def construct(in_left, in_right):
        if in_left > in_right:
            return None
        root_val = preorder.pop(0)
        root = TreeNode(root_val)
        mid = position[root_val]
        root.left = construct(in_left, mid - 1)
        root.right = construct(mid + 1, in_right)
        return root
    
    return construct(0, len(inorder) - 1)

106. Construct Binary Tree from Inorder and Postorder Traversal

Approach: Postorder places root last (left-right-root). Locate root in inorder to partition subtrees.

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

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None
    
    index_map = {val: idx for idx, val in enumerate(inorder)}
    
    def build(i, j):
        if i > j:
            return None
        root_val = postorder.pop()
        root = TreeNode(root_val)
        idx = index_map[root_val]
        root.right = build(idx + 1, j)
        root.left = build(i, idx - 1)
        return root
    
    return build(0, len(inorder) - 1)

889. Construct Binary Tree from Preorder and Postorder Traversal

Approach: Preorder is root-left-right, postorder is left-right-root. The element after root in preorder is the left subtree's root, which can split postorder.

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

def constructFromPrePost(preorder, postorder):
    def construct(pre, post):
        if not pre or not post:
            return None
        size = len(pre)
        if size == 1:
            return TreeNode(post[0])
        left_subtree_size = post.index(pre[1]) + 1
        left_child = construct(pre[1:1 + left_subtree_size], post[:left_subtree_size])
        right_child = construct(pre[1 + left_subtree_size:], post[left_subtree_size:-1])
        return TreeNode(pre[0], left_child, right_child)
    
    return construct(preorder, postorder)

2583. Kth Largest Level Sum in Binary Tree

Approach: BFS for level-order traversal, compute sums per level. Maintain a min-heap of size K to track largest K sums.

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

def kthLargestLevelSum(root, k):
    import heapq
    min_heap = []
    queue = [root]
    
    while queue:
        level_size = len(queue)
        level_sum = 0
        next_level = []
        for node in queue:
            level_sum += node.val
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        if len(min_heap) < k or min_heap[0] < level_sum:
            heapq.heappush(min_heap, level_sum)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
        queue = next_level
    
    return min_heap[0] if len(min_heap) == k else -1

2476. Closest Nodes Queries in Binary Search Tree

Approach: Extract sorted values via inorder traversal. Use binary search for each query to find nearest smaller and larger values.

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

def closestNodes(root, queries):
    import bisect
    values = []
    
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        values.append(node.val)
        inorder(node.right)
    
    inorder(root)
    result = []
    
    for q in queries:
        idx = bisect.bisect_left(values, q)
        larger = values[idx] if idx < len(values) else -1
        if idx == len(values) or values[idx] != q:
            idx -= 1
        smaller = values[idx] if idx >= 0 else -1
        result.append([smaller, larger])
    
    return result

235. Lowest Common Ancestor in Binary Search Tree

Approach: BST property ensures root value is either between both nodes' values or matches one. Traverse accordingly until meeting condition.

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

def lowestCommonAncestor(root, p, q):
    while root:
        if root.val < p.val and root.val < q.val:
            root = root.right
        elif root.val > p.val and root.val > q.val:
            root = root.left
        else:
            return root