Tree And Linked Structure Algorithms

What's being tested

Microsoft interviewers are probing tree/graph traversal fluency, mutable node-structure design, and the ability to pick the right representation for read/write tradeoffs. You should be able to code clean recursive and iterative traversals, reason about parent pointers and cycles, and explain complexity under dynamic updates.

Patterns & templates

• DFS traversal templates — preorder, inorder, postorder; recursive is concise, iterative uses explicit stack; time O(n), space O(h) or O(n).

• BFS / level order — use queue, process by level_size; reverse printing can prepend levels or collect then reverse; time O(n).

• Lowest common ancestor — BST uses value ordering in O(h); general binary tree uses postorder recursion returning “found p/q” in O(n).

• Mutable tree API design — addChild, removeChild, parent, children; guard against duplicate parents, detached subtrees, and accidental cycles.

• Subtree aggregate counts — maintain subtree_size or subordinate counts on ancestor path updates; read O(1), move/update O(h) unless indexed.

• Serialization/deserialization — encode null markers for binary trees or child counts for generic trees; validate malformed input and preserve traversal order.

• Dynamic programming for LPS — dp[i][j] over substring bounds; recurrence depends on s[i] == s[j]; time O(n^2), space O(n^2) or optimized.

Common pitfalls

Pitfall: Treating every tree as a BST. LCA, traversal order, and search complexity change completely without ordering guarantees.

Pitfall: Forgetting cycles in “generic tree” APIs. A mutable node structure can become a graph unless addChild validates ancestry.

Pitfall: Giving only recursive solutions. Interviewers often ask for iterative DFS/BFS to test stack-safety and production readiness.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.