Tree And Linked Structure Algorithms
Asked of: Software Engineer
Last updated

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 explicitstack; timeO(n), spaceO(h)orO(n). -
BFS / level order — use
queue, process bylevel_size; reverse printing can prepend levels or collect then reverse; timeO(n). -
Lowest common ancestor — BST uses value ordering in
O(h); general binary tree uses postorder recursion returning “found p/q” inO(n). -
Mutable tree API design —
addChild,removeChild,parent,children; guard against duplicate parents, detached subtrees, and accidental cycles. -
Subtree aggregate counts — maintain
subtree_sizeor subordinate counts on ancestor path updates; readO(1), move/updateO(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 ons[i] == s[j]; timeO(n^2), spaceO(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
addChildvalidates 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.
Featured in interview prep guides
Practice questions
- Design read-heavy org chart subordinate countsMicrosoft · Software Engineer · Onsite · medium
- Populate next pointers in a perfect binary treeMicrosoft · Software Engineer · Onsite · medium
- Solve binary-tree reverse printing and LPSMicrosoft · Software Engineer · Technical Screen · easy
- Find lowest common ancestor in treeMicrosoft · Software Engineer · Technical Screen · medium
- Reverse linked list in fixed-size groupsMicrosoft · Software Engineer · Onsite · medium
- Implement tree traversals, BFS, and subsets generationMicrosoft · Software Engineer · Onsite · Medium
- Implement a generic tree Node classMicrosoft · Software Engineer · Onsite · Medium
Related concepts
- Trees, Linked Lists, And Pointer AlgorithmsCoding & Algorithms
- Trees And Hierarchical StructuresCoding & Algorithms
- Trees, Recursion, And BST TraversalCoding & Algorithms
- Trees, Tries, and Hierarchical DataCoding & Algorithms
- Tree Traversal And Hierarchical StructuresCoding & Algorithms
- BST Algorithms And Lowest Common AncestorCoding & Algorithms