Lowest common ancestor, serialisation and balanced trees

Lowest common ancestor

An ancestor of a node is any node on the path from the root down to it, including the node itself. The lowest common ancestor of p and q is the deepest node that is an ancestor of both. In a family tree it is the closest shared grandparent; in a folder tree it is the deepest folder that contains both files; in an org chart it is the lowest manager both people report up to.

LCA in a BST: follow the split

In a BST the values tell you where to go. If both p and q are smaller than the current node, the LCA is in the left subtree. If both are larger, it is in the right subtree. Otherwise they split here (one on each side, or one of them IS this node), so the current node is the LCA. This walks one path: O(h) time and O(1) space with a loop.

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

bst = build([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
print(lca_bst(bst, 2, 8), lca_bst(bst, 2, 4), lca_bst(bst, 3, 5))   # Output: 6 2 4

LCA in any binary tree

Without the BST order you must search. Ask each subtree: "did you find p or q?" A subtree returns the matching node if it found one, or None. If the current node is p or q, return it at once. If BOTH the left and right calls return something, p and q are on different sides, so the current node is the LCA. If only one side returns something, pass that up. Every node is visited at most once: O(n) time, O(h) space.

def lca(node, p, q):
    if node is None or node.val == p or node.val == q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node            # p and q are on different sides
    return left or right

t = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(lca(t, 5, 1).val, lca(t, 5, 4).val, lca(t, 7, 8).val)   # Output: 3 5 3

Serialise and deserialise

Serialising means turning a structure into a string (or bytes) so it can be saved to a file, stored in a database or sent over a network. Deserialising rebuilds the same structure from the string. A plain preorder list is not enough: [1, 2] could mean "2 is the left child" or "2 is the right child". Adding a marker such as "#" for every missing child removes the doubt, and then preorder alone describes the tree exactly.

def serialize(root):
    parts = []
    def walk(node):
        if node is None:
            parts.append("#")
            return
        parts.append(str(node.val))
        walk(node.left)
        walk(node.right)
    walk(root)
    return ",".join(parts)

def deserialize(data):
    tokens = iter(data.split(","))
    def make():
        tok = next(tokens)
        if tok == "#":
            return None
        node = TreeNode(int(tok))
        node.left = make()       # the same order as serialize: node, left, right
        node.right = make()
        return node
    return make()

s = serialize(build([1, 2, 3, None, None, 4, 5]))
print(s)                                   # Output: 1,2,#,#,3,4,#,#,5,#,#
print(serialize(deserialize(s)) == s)      # Output: True

Level order with markers works too (that is how LeetCode shows trees and how build() reads them). JSON with nested objects is another common choice in APIs.

Keeping trees balanced

A plain BST can become a chain. Self-balancing BSTs reshape themselves after every insert and delete so the height stays O(log n), which makes search, insert and delete O(log n) in the worst case. They use rotations: a small local change of links that keeps the BST order but moves one node up and another down.

    y                x
   / \             /   \
  x   C    -->    A     y
 / \                   / \
A   B                 B   C

• AVL tree: keeps the strict rule that the two subtree heights of every node differ by at most 1. After an insert or delete it walks back up and fixes any broken node with one or two rotations. Very well balanced, so lookups are fast.
• Red-black tree: colours every node red or black and follows a few colour rules, which guarantee that the longest root-to-leaf path is at most twice the shortest. Slightly less balanced than AVL, but usually fewer rotations on updates. Java's TreeMap and TreeSet are red-black trees, and C++ std::map and std::set are usually implemented as red-black trees.

In interviews you are rarely asked to code AVL or red-black trees from memory. Know what they guarantee (O(log n) height), the idea of a rotation, and where they are used. Python has no balanced tree in its standard library; people use dict and set for lookups, a sorted list with bisect for ordered data, or a third-party package for a sorted container.

B-trees: balanced trees for disks

Reading from a disk or SSD is slow compared with memory, and it reads a whole block (page) at a time. A B-tree stores many keys in each node, often hundreds, so each node fills a page and the tree is very wide and very shallow. A few levels can index millions of rows, so a lookup needs only a few page reads. That is why most relational databases use B-trees (or the B+ tree variant) for their indexes: PostgreSQL's default index type is B-tree, and MySQL's InnoDB stores tables and indexes as B+ trees. File systems use them too.

Common mistakes

• In the BST LCA, forgetting the case where p or q equals the current node. Fix: use "otherwise return node" after the two "both smaller" and "both larger" checks.
• Using the BST shortcut on a general binary tree. Fix: only follow values left or right when the tree is promised to be a BST.
• Serialising without null markers, or deserialising in a different order than you serialised. Fix: write and read in the same preorder, with a marker for every None.
• Splitting on a comma but storing values that contain commas (for example names). Fix: pick a safe separator, escape it, or use JSON.
• Saying a BST lookup is always O(log n). Fix: say O(h); it is O(log n) only for a balanced tree such as AVL or red-black.