traversal on Binary Tree

Question

Perform a partitioning on a binary tree and return the result.

Codemia · Accepted Answer

The problem involves performing a partitioning operation on a binary tree, which suggests a traversal-based approach. Given that we need to examine nodes and possibly restructure or collect them based on certain criteria, Depth-First Search (DFS) is the most suitable pattern here. DFS allows us to explore each branch of the tree fully before backtracking, making it easy to gather and partition nodes based on their values or other properties.

1. **Define the Partition Condition**: Decide the criteria for partitioning. For example, if partitioning based on node values, we can create two partitions: one for values less than a threshold and one for values greater or equal.  
2. **Recursive DFS Function**: Implement a recursive function that visits each node. For each node, check if it meets the partitioning condition and add it to the corresponding partition list.  
3. **Return the Results**: After traversing the entire tree, return the two partitioned lists.  
**Example**: Given a binary tree:  
```
      5
     / \
    3   8
   / \   \
  1   4   9
```
If the partitioning condition is `val < 5`, the result would be: `Less than 5: [3, 1, 4], Greater or equal to 5: [5, 8, 9]`.

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def partition_tree(root, threshold):
    less_than = []
    greater_or_equal = []

def dfs(node):
        if node is None:
            return
        if node.val < threshold:
            less_than.append(node.val)
        else:
            greater_or_equal.append(node.val)
        dfs(node.left)
        dfs(node.right)

dfs(root)
    return less_than, greater_or_equal
```
This implementation recursively traverses the tree, partitioning node values into two lists based on the provided threshold.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once during the DFS traversal. The space complexity is also O(n) in the worst case, where all nodes are stored in one of the partitions, particularly when the tree is skewed (like a linked list).

1. **Empty Tree**: If the input tree is empty (i.e., root is None), the function should return two empty lists.  
2. **Single Node Tree**: If the tree contains a single node, the output should depend on whether that node's value meets the partitioning condition.  
3. **All Nodes Meet One Condition**: If all nodes are less than or greater than the threshold, ensure the corresponding list captures all nodes correctly.  
4. **Negative Values**: The algorithm should handle negative values correctly in the partitioning process.

traversal on Binary Tree

HubSpot

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

HubSpot 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