cswork / libraryOpen practice workspace

Interview questions · Microsoft

Implement tree traversals, BFS, and subsets generation

This question evaluates proficiency with fundamental data structures and algorithms—binary tree traversals (preorder, inorder, postorder), breadth-first search on unweighted graphs, and power-set/subset generation—emphasizing implementation choices between recursive and iterative approaches and required time and space complexity reasoning.

  1. Define a TreeNode class for a binary tree with an integer value and left/right pointers. Implement preorder, inorder, and postorder traversals: (a) recursive versions; (b) iterative versions using an explicit stack (you may use two stacks for postorder). Return the traversal orders as lists and analyze time and space complexity.
  2. Given an unweighted graph as an adjacency list and a source node s, implement BFS to return the visitation order, a distance map of minimum edge distances from s, and a parent map to reconstruct shortest paths. Handle disconnected graphs by describing how to traverse all components and produce results for each.
  3. Given an array of distinct integers nums, generate the power set (all subsets). Provide (a) a backtracking solution; and (b) an iterative solution using for-loops only (no recursion), explaining how subsets are built layer by layer. Return subsets in any order and analyze complexity.

Community answers

Nothing here yet.

Join in on CSWork →