compression on Binary Tree
Last updated: August 28, 2025
Quick Overview
Given a binary tree, implement a function to compress the tree into a more compact representation by removing all nodes that do not contribute to the path from the root to any leaf node. The output should be a new binary tree that retains only the necessary nodes, and the function should return the root of this compressed tree.
Expedia
August 28, 2025202
7
2,073 solved
Given a binary tree, implement a function to compress the tree into a more compact representation by removing all nodes that do not contribute to the path from the root to any leaf node. The output should be a new binary tree that retains only the necessary nodes, and the function should return the root of this compressed tree.
Coding interviews at Expedia focus on problem-solving approach as much as the final solution. The interviewer wants to see you break down the problem, consider edge cases, and optimize iteratively. Communication throughout the process is key.
What the Interviewer Expects
- Recognize the underlying problem pattern (sliding window, two pointers, BFS/DFS, etc.)
- Discuss multiple approaches and trade-offs before coding
- Implement an optimal solution with clean, production-quality code
- Handle all edge cases including boundary conditions and invalid input
- Optimize both time and space complexity with clear justification
- Test your solution systematically with well-chosen examples
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- Can you optimize the space complexity of your solution?
- What if the input doesn't fit in memory?
- How would your solution change if the input was sorted?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
The problem requires us to compress a binary tree by retaining only the nodes that contribute to the path from the root to any leaf node. This scenario suggests a depth-first search (DFS) approach, as...
Approach
- Recursive DFS Function: Create a recursive function that traverses the tree. For each node:
- Check if it is a leaf node (both left and right children are None). If it is, return this node. ...
Submit Your Answer
