Home/Data Structures & Algorithms/Trees, BSTs & Hierarchical Indexes
  1. Asked: September 11, 2026In: ,

    Lowest Common Ancestor: Why Binary Lifting in O(log N) beats naive DFS in high-scale DAGs

    Anonymous
    Anonymous Begginer

    When you have multiple online LCA queries on a static tree, the gold standard is Binary Lifting (used in compiler dominance frontiers, distributed network routing, and Git commit histories). 1. The Core Idea: Powers of 2 Parent Jumps Instead of storing only a node's immediate parent (which forces yoRead more

    When you have multiple online LCA queries on a static tree, the gold standard is Binary Lifting (used in compiler dominance frontiers, distributed network routing, and Git commit histories).

    1. The Core Idea: Powers of 2 Parent Jumps

    Instead of storing only a node’s immediate parent (which forces you to step up the tree one node at a time in $O(N)$), what if every node stored its ancestor at distance $2^0, 2^1, 2^2, 2^3, dots, 2^k$?

    We define a 2D table: up[u][i] = the (2^i)-th ancestor of node u.

    The state transition is pure dynamic programming:

    up[u][i] = up[ up[u][i-1] ][i-1]

    In English: ‘To jump $2^i$ steps up from $u$, first jump $2^{i-1}$ steps up to reach intermediate node $v$, and then from $v$ jump another $2^{i-1}$ steps!’ ($2^{i-1} + 2^{i-1} = 2^i$).

    2. Answering an LCA Query in 2 Steps

    To find the LCA of nodes u and v:

    1. Level the Depths: If depth[u] < depth[v], swap them. Use binary powers to jump u upwards until depth[u] == depth[v] in $O(log N)$ steps. If u == v, they were on the same branch → return u!
    2. Simultaneous Binary Leap: Jump both u and v upwards together using the largest possible power of 2 such that their ancestors are still different (up[u][i] != up[v][i]). When no more jumps can be made, their immediate parent (up[u][0]) is their Lowest Common Ancestor!

    Clean C++20 Implementation

    #include <vector>
#include <cmath>
#include <algorithm>

class TreeLCA {
    int n, max_log;
    std::vector<int> depth;
    std::vector<std::vector<int>> up;

    void dfs(int u, int p, int d, const std::vector<std::vector<int>>& adj) {
        depth[u] = d;
        up[u][0] = p;
        for (int i = 1; i < max_log; ++i) {
            up[u][i] = up[ up[u][i - 1] ][i - 1];
        }
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1, adj);
            }
        }
    }

public:
    TreeLCA(int nodes, int root, const std::vector<std::vector<int>>& adj) : n(nodes) {
        max_log = std::ceil(std::log2(n)) + 1;
        depth.assign(n, 0);
        up.assign(n, std::vector<int>(max_log, root));
        dfs(root, root, 0, adj);
    }

    int queryLCA(int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);

        // Step 1: Bring u and v to same depth
        int diff = depth[u] - depth[v];
        for (int i = 0; i < max_log; ++i) {
            if ((diff >> i) & 1) {
                u = up[u][i];
            }
        }
        if (u == v) return u;

        // Step 2: Jump together
        for (int i = max_log - 1; i >= 0; --i) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
};

    Complexity Breakdown

    • Preprocessing Time: O(N log N) via a single DFS pass.
    • Preprocessing Memory: O(N log N) to store the jump table.
    • Per Query Time: Strictly O(log N). For $N = 1,000,000$, $log_2(1,000,000) pprox 20$ operations. You can evaluate 50,000 queries in a fraction of a second!
    See less
    • 0
  2. Asked: September 11, 2026In: ,

    How to traverse a Binary Tree in O(1) memory without recursion or stack (Morris Traversal)?

    Abhay Tiwari
    Abhay Tiwari Begginer

    Morris Traversal is one of the most brilliant algorithms in computer science. It solves the exact constraint you're facing: how do you traverse a tree without spending any extra memory on a stack? 1. The Core Secret: Threaded Binary Trees When you are at a node and go deep into its left subtree, howRead more

    Morris Traversal is one of the most brilliant algorithms in computer science. It solves the exact constraint you’re facing: how do you traverse a tree without spending any extra memory on a stack?

    1. The Core Secret: Threaded Binary Trees

    When you are at a node and go deep into its left subtree, how do you get back up to the node without a parent pointer or call stack? Normally, you need a stack to remember the return path.

    J. H. Morris realized something clever: in every binary tree, about half of all pointers are NULL! Every leaf node has a null right child that is sitting there doing nothing.

    Morris repurposes these unused null pointers as temporary bridge wires (called “threads”) back to the inorder successor:

    1. Find the node’s inorder predecessor (the rightmost node in the left subtree).
    2. If its right pointer is null, point it back to the current node: predecessor->right = current. Then move current = current->left.
    3. If its right pointer is already pointing to current, that means you have already finished visiting the left subtree! You print/record current->val, restore the pointer to null (repairing the tree), and move current = current->right!

    When the algorithm finishes, the tree is 100% restored to its original state. Zero memory allocated, zero permanent mutations!

    Clean C++20 Morris Inorder Traversal

    #include <vector>
#include <cstdint>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> morrisInorderTraversal(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;

    while (curr != nullptr) {
        if (curr->left == nullptr) {
            // Case 1: No left child, visit this node and move right
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            // Case 2: Find inorder predecessor (rightmost in left subtree)
            TreeNode* pred = curr->left;
            while (pred->right != nullptr && pred->right != curr) {
                pred = pred->right;
            }

            if (pred->right == nullptr) {
                // First time visiting: create temporary thread
                pred->right = curr;
                curr = curr->left;
            } else {
                // Second time visiting: restore tree and visit curr
                pred->right = nullptr;
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

    Complexity & Trade-offs

    • Time Complexity: O(N). Even though we search for predecessors, each edge in the tree is traversed at most 3 times (once to find predecessor, once to create thread, once to remove thread). 3 * (N - 1) = O(N).
    • Space Complexity: O(1) auxiliary space. Just two pointers (curr and pred). No call stack, no heap allocations.
    • Thread-Safety Warning: Because Morris Traversal temporarily mutates right pointers during execution, it is not safe for concurrent readers on the same tree instance. If multiple threads read the tree simultaneously, use standard recursive DFS with a large stack or an explicit thread-local queue.
    See less
    • 0