rotation on Binary Tree

Question

Given a binary tree, implement a function to perform a rotation operation on the tree at a specified node. The rotation should either be a left or right rotation, depending on the input parameter, and the function should return the new root of the modified tree. Ensure that your solution maintains the properties of the binary tree and handles edge cases such as null nodes or single-child nodes.

Codemia · Accepted Answer

To perform a rotation operation on a binary tree at a specified node, we can utilize tree restructuring techniques. The specific pattern that applies here is a recursive tree manipulation. In a binary tree, a left rotation around a node involves making the right child of the node the new root of the subtree and promoting the original node to be the left child of this new root. Conversely, a right rotation involves making the left child the new root and the original node the right child. This pattern is crucial because it allows us to maintain the properties of the binary tree while altering its structure.

The algorithm can be broken down into the following steps: 1. Identify the node at which to perform the rotation. If the node is null, return null. 2. Depending on the rotation direction (left or right), perform the appropriate restructuring: 
   - **Left Rotation**: 
     a. Set `new_root` to the right child of the specified node. 
     b. Set the right child of the specified node to the left child of `new_root`. 
     c. Set the left child of `new_root` to the specified node. 
   - **Right Rotation**: 
     a. Set `new_root` to the left child of the specified node. 
     b. Set the left child of the specified node to the right child of `new_root`. 
     c. Set the right child of `new_root` to the specified node. 
3. Return the `new_root` of the subtree.

Here is the Python implementation for the rotation operation:

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

def rotateBinaryTree(root, target, direction):
    if root is None or target is None:
        return root

if direction == 'left':
        new_root = target.right
        target.right = new_root.left
        new_root.left = target
    elif direction == 'right':
        new_root = target.left
        target.left = new_root.right
        new_root.right = target
    else:
        return root  # Invalid direction

return new_root
```

The time complexity of this operation is O(1) since we are only performing a constant number of operations regardless of the size of the tree, as we are not traversing the tree. The space complexity is also O(1) because we are using a fixed amount of space for variables and not utilizing any additional data structures.

1. **Null Nodes**: If the specified node or the root is null, the function should return null without performing any operations. 
2. **Single-Child Nodes**: If the node to be rotated has no right child (for left rotation) or no left child (for right rotation), the function should adjust appropriately without causing a pointer error. 
3. **Root Rotation**: If the target node is the current root, the function should correctly return the new root after the rotation. 
4. **Invalid Direction**: If an invalid rotation direction is provided, the function should return the original root.

rotation on Binary Tree

Morgan Stanley

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

Morgan Stanley 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