compression on Binary Tree

Question

Given a binary tree, compress the tree by removing all nodes that have only one child, and return the modified tree. The output should maintain the original structure of the tree while ensuring that all nodes with a single child are eliminated.

Codemia · Accepted Answer

This problem can be approached using Depth-First Search (DFS). The reason DFS is applicable here is that we need to traverse each node of the binary tree while deciding whether to keep or remove nodes based on their children. The specific pattern involves modifying the tree in place and ensuring that we only retain nodes that have at least two children. This requires a post-order traversal approach, where we first handle the children of a node before making decisions about the node itself.

1. Start with a DFS function that takes a node as input.  
2. If the node is null, return null.  
3. Recursively call DFS on the left and right children of the node.  
4. After the recursive calls, check the results:  
   - If the left child is null and the right child is not, return the right child (remove the left child).  
   - If the right child is null and the left child is not, return the left child (remove the right child).  
   - If both children exist, return the current node.  
5. The traversal will ensure that all nodes with one child are eliminated, maintaining the structure of the tree with only the necessary nodes.

**Example:**  
Given the tree:  
```
       1
      / \
     2   3
      \
       4
```
After processing, node 2 will be replaced by 4, resulting in:  
```
       1
      / \
     3   4
```

Here is the Python implementation of the described approach:
```python
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Solution:
    def compressTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        root.left = self.compressTree(root.left)
        root.right = self.compressTree(root.right)
        
        if not root.left and root.right:
            return root.right
        elif not root.right and root.left:
            return root.left
        return root
```
This code recursively compresses the binary tree as specified.

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once. The space complexity is O(h), where h is the height of the tree due to the recursion stack. In the worst case, for a skewed tree (like a linked list), h could be O(n), but for a balanced tree, it would be O(log n).

1. **Empty Tree**: If the input tree is null, the output should also be null.  
2. **Single Child Nodes**: A tree where each node has only one child (like a linked list) should return a tree with only the last node.  
3. **All Nodes with Two Children**: A fully balanced tree should remain unchanged since no nodes will be removed.  
4. **Complex Structures**: Trees with varying numbers of children should be handled correctly, for instance, one side being a complete binary tree and the other being a linear chain.

compression on Binary Tree

CrowdStrike

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

CrowdStrike Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string