partitioning on Binary Tree

Question

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

Codemia · Accepted Answer

To solve the problem of performing a rotation on a binary tree, we need to recognize that the operation could be akin to tree restructuring, similar to a rotation in a linked list. The primary pattern we can utilize here is Depth-First Search (DFS) for traversing the tree recursively. This is relevant because we need to access nodes in a structured manner and potentially reorganize child nodes based on the rotation logic, which can be efficiently managed using recursive calls.

The core idea is to define a function that rotates the binary tree around a specified node. We will approach this by using DFS to traverse to the desired node and then rearranging the pointers accordingly. For example, if we want to perform a right rotation around a node, the left child of that node becomes the new root of the subtree, and the original node becomes the right child of the new root.

1. Define a recursive function `rotate(node)` that checks if the node is null. If it is, return null.
2. If the node matches the node we want to rotate around, perform the rotation:
   - Store the left child of the node as the new root.
   - Set the left child of the new root to the node itself.
   - Set the right child of the original node as the new root's right child.
3. Recursively call `rotate()` on the left and right children of the current node to rotate other parts of the tree if necessary.
4. Return the new root after rotation.

Here is a sample Python implementation for the rotation of a binary tree around a specified node:

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

class Solution:
    def rotate(self, root: TreeNode, target: TreeNode) -> TreeNode:
        if not root:
            return None
        if root == target:
            new_root = root.left
            root.left = new_root.right if new_root else None
            if new_root:
                new_root.right = root
            return new_root
        root.left = self.rotate(root.left, target)
        root.right = self.rotate(root.right, target)
        return root
```
This code handles the rotation by checking if the current node is the target and rearranging pointers accordingly.

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree. This is because we potentially visit each node once during the DFS traversal. The space complexity is O(h), where h is the height of the tree, due to the call stack used by the recursive function. In the worst case, for a skewed tree, h can be equal to n, but for a balanced tree, h would be log(n). This is efficient given the constraints of a binary tree.

We need to consider several edge cases while implementing the solution:
1. If the tree is empty (i.e., root is null), the function should return null immediately.
2. If the target node to rotate around does not exist in the tree, the function should return the original tree without any modification.
3. If the target node has no left child, a rotation would not change the structure of the tree, so this should be handled gracefully. 
4. If the target node is a leaf node, the function should also return the tree as is since rotation would not apply.

partitioning on Binary Tree

Apple

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

Apple 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