Trees and Binary Search Trees Questions

To do iterative inorder traversal, I use an explicit stack to simulate the recursion stack. The idea is to keep walking left, pushing nodes as I go, then pop the last node, visit it, and move to its right child.

def inorder_traversal(root):
    result = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

This is especially useful for deep trees because it avoids Python recursion depth limits. For a BST, the output is sorted because inorder visits nodes in ascending order.

Time: O(n)
Space: O(h), where h is tree height.

I’d design this as a tree service with a transactional source of truth plus read-optimized indexes.

API

• POST /nodes insert child under parent
• DELETE /nodes/{id} remove node or subtree
• GET /nodes/{id} fetch node
• GET /nodes/{id}/subtree return descendants
• GET /nodes/{id}/ancestors return lineage
• POST /serialize and POST /deserialize for persistence/import

Storage model

• Canonical table: adjacency list with id, parent_id, payload, version
• Optional read models:
  • path enumeration for ancestor queries
  • closure table for fast subtree/ancestor lookups

Consistency

• Enforce one parent per node with foreign keys and transactions.
• Prevent cycles by validating ancestry before insert/update.
• Use optimistic locking on version for concurrent edits.

Tradeoffs

• Adjacency list: simplest writes, slower hierarchy reads.
• Closure table: fast subtree/ancestor queries, heavier writes.
• Materialized path: good for prefix scans, harder reparenting.

For a backend team, I’d keep the write path simple and use asynchronous index maintenance if subtree and ancestor queries are frequent. Serialization should be versioned and schema-aware so old clients can still read new trees safely.

Preorder visits the root first, then left subtree, then right subtree. A backend engineer might use it to serialize a tree structure, such as exporting a menu or permission hierarchy.

Inorder visits left, then root, then right. For a BST, this returns values in sorted order, which is useful for generating ordered reports or debugging stored keys.

Postorder visits left, then right, then root. It is useful when deleting a tree or freeing resources because children are processed before the parent.

Level-order visits nodes level by level using a queue, from top to bottom and left to right. In production, this is useful for breadth-first inspection, such as finding the nearest matching node or processing tiers in a dependency tree.

For a general binary tree, I’d use a postorder recursion that returns whether the current subtree contains either target node. The first node where left and right subtrees split the targets, or where the current node is one target and the other is below it, is the LCA.

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

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        self.ans = None

        def dfs(node):
            if not node:
                return False

            left = dfs(node.left)
            right = dfs(node.right)
            mid = node == p or node == q

            if mid + left + right >= 2:
                self.ans = node

            return mid or left or right

        dfs(root)
        return self.ans

Why this works

• Each call reports whether p or q exists in that subtree
• If two of {mid, left, right} are true, current node is the split point
• Works even when nodes are in different subtrees or one is ancestor of the other

Complexity

• Time: O(n)
• Space: O(h) recursion depth

Edge cases

• Same node for both inputs
• One node missing from tree
• Empty tree

In production, I’d confirm whether inputs are guaranteed present; if not, I’d return None unless both are found.

To delete from a BST, I’d recurse until I find the node, then handle the three structural cases separately.

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

class Solution:
    def deleteNode(self, root, key):
        if not root:
            return None

        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left

            # Two children: replace with inorder successor
            succ = root.right
            while succ.left:
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)

        return root

Cases

• Leaf: return None
• One child: return that child directly
• Two children: replace with inorder successor (smallest value in right subtree)

Why successor works
It preserves the BST ordering: everything in the left subtree stays smaller, and everything in the right subtree stays larger.

Complexity

• Time: O(h)
• Space: O(h) recursion depth

In backend systems, I’d also consider rebalancing if this tree is part of a long-lived in-memory index, because repeated deletes can make the tree skewed.