Implement tree traversals, BFS, and subsets generation

Q: Implement tree traversals, BFS, and subsets generation

This is a Coding & Algorithms interview question from Microsoft for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.
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.
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.

Implement tree traversals, BFS, and subsets generation

Comments (0)