DSA Series · Trees · Part 5

Tree Algorithms & Interview Patterns

March 2026 · 10 min read

Height of a Tree

int height(TreeNode* node) {
    if (!node) return -1;
    return 1 + std::max(height(node->left), height(node->right));
}

▶ Height Computation Animation

Watch the recursive bottom-up height calculation. Each node computes: 1 + max(left height, right height).

Lowest Common Ancestor (LCA)

Lowest Common Ancestor, the deepest node that is an ancestor of both targets.

// BST-specific LCA
TreeNode* lcaBST(TreeNode* root, int p, int q) {
    if (p < root->val && q < root->val)
        return lcaBST(root->left, p, q);
    if (p > root->val && q > root->val)
        return lcaBST(root->right, p, q);
    return root;
}

// General tree LCA
TreeNode* lcaGeneral(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    auto* left = lcaGeneral(root->left, p, q);
    auto* right = lcaGeneral(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

▶ LCA Finding Animation

Click two target nodes, then watch the algorithm find their Lowest Common Ancestor.

Pick a pair to animate

Diameter of a Tree

The diameter is the longest path between any two nodes (may or may not pass through root).

int diameter(TreeNode* root) {
    int result = 0;
    std::function<int(TreeNode*)> depth = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int L = depth(node->left);
        int R = depth(node->right);
        result = std::max(result, L + R);
        return 1 + std::max(L, R);
    };
    depth(root);
    return result;
}

▶ Diameter Visualization

See the longest path between any two nodes highlighted step by step.

Serialize / Deserialize

std::string serialize(TreeNode* root) {
    if (!root) return "#,";
    return std::to_string(root->val) + "," +
           serialize(root->left) + serialize(root->right);
}

TreeNode* deserialize(std::istringstream& stream) {
    std::string token;
    if (!std::getline(stream, token, ',') || token == "#")
        return nullptr;
    auto* node = new TreeNode(std::stoi(token));
    node->left = deserialize(stream);
    node->right = deserialize(stream);
    return node;
}

Complexity Summary

Operation	BST (average)	BST (worst)	AVL / Balanced
Search	O(log n)	O(n)	O(log n)
Insert	O(log n)	O(n)	O(log n)
Delete	O(log n)	O(n)	O(log n)
Traversal	O(n)	O(n)	O(n)
Space	O(n)	O(n)	O(n)
Height	O(log n) expected	O(n)	O(log n) guaranteed

Interview Patterns

Pattern recognition: Most tree problems reduce to one of these strategies.

DFS recursion: Height, diameter, path sum, subtree problems. Think "what info does each subtree return upward?"
BFS level-order: Level averages, zigzag traversal, right-side view, minimum depth.
Build from traversals: Construct tree from pre-order + in-order, or from sorted array (balanced BST).
Two-pointer on BST: In-order iterator + reverse iterator for pair-sum problems.
Morris traversal: O(1) space in-order traversal by threading the tree.

Morris In-order Traversal (O(1) space)

void morrisInorder(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            visit(cur);
            cur = cur->right;
        } else {
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur)
                pred = pred->right;
            if (!pred->right) {
                pred->right = cur;
                cur = cur->left;
            } else {
                pred->right = nullptr;
                visit(cur);
                cur = cur->right;
            }
        }
    }
}

Summary

Key algorithms: height, LCA, diameter, serialization.
Morris traversal achieves O(1) space by temporarily threading the tree.
Most interview problems are DFS recursion or BFS level-order in disguise.
AVL guarantees O(log n) worst-case for all operations.