**π‘ Problem Formulation:** When working with binary trees in Python, there may be scenarios where changing the root of the tree while preserving the rest of the structure is necessary. This modification has various applications, such as optimizing search algorithms or re-structuring data. For instance, if we have a binary tree with a root value of ‘1’, and we want to change the root to ‘2’, which is currently a child of ‘1’, we need an effective method to perform this shift while maintaining the binary tree’s properties. This article explores various solutions to achieve the desired outcome.

## Method 1: Recursive Re-rooting

This method involves using a recursive approach to traverse the tree and shift the root. The function modifies the parent-child relationships such that the new root is placed at the top and its children are adjusted accordingly, without creating any new nodes, thus conserving the original structure of the tree. Effectively, it redefines the parent of the current root as its child while rerooting the tree.

Here’s an example:

class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right def change_root(old_root, new_root): def dfs(node, parent): if node: dfs(node.left, node) dfs(node.right, node) if parent and parent.value == new_root.value: node.left, node.right, parent.left = node.right, parent, node.left return node return dfs(old_root, None) # Example Usage original_root = TreeNode(1, TreeNode(2), TreeNode(3)) new_root = original_root.left new_tree_root = change_root(original_root, new_root)

The output will be a new tree with the node ‘2’ as its root.

In this snippet, we define a function `change_root()`

that takes the current root and the desired new root as arguments. The nested `dfs()`

function (depth-first search) is called recursively to traverse the tree and update the parent-child relationships accordingly when the new root is found.

## Method 2: Iterative Tree Re-rooting

The iterative method to change the root of a binary tree involves an iterative deepening approach. It uses a while loop and parent pointers to successively move up the tree, swapping parent and child until the new root node is positioned at the top of the tree structure.

Here’s an example:

def reroot_iteratively(old_root, new_root_value): node = old_root parent = None last = None while node.value != new_root_value: next_node = node.left if node.left and node.left.value != last else node.right node.left, node.right, parent, last = parent, last, node, node.value node = next_node return parent # Example Usage original_root = TreeNode(1, TreeNode(2), TreeNode(3)) new_tree_root = reroot_iteratively(original_root, 2)

The output will have ‘2’ as the new root of the tree.

The code defines a `reroot_iteratively()`

function that iterates through the nodes until it reaches the new root, inverting the left and right children while using variables to keep track of the previous parent and last seen node. Finally, `parent`

, the new root, is returned.

## Method 3: Mirror and Adjust

This method consists of mirroring the binary tree on the path from the old root to the new root, then correcting the left and right pointers as necessary to ensure a proper binary tree structure is maintained after the re-rooting.

Here’s an example:

def reroot_mirror(old_root, new_root_value): if old_root.value == new_root_value: return old_root if old_root.left and old_root.left.value == new_root_value: new_root = old_root.left old_root.left = new_root.right new_root.right = old_root return new_root elif old_root.right and old_root.right.value == new_root_value: new_root = old_root.right old_root.right = new_root.left new_root.left = old_root return new_root else: if old_root.left: left_result = reroot_mirror(old_root.left, new_root_value) if left_result: if old_root.left == left_result: old_root.left = None return left_result if old_root.right: right_result = reroot_mirror(old_root.right, new_root_value) if right_result: if old_root.right == right_result: old_root.right = None return right_result return None # Example Usage original_root = TreeNode(1, TreeNode(2), TreeNode(3)) new_tree_root = reroot_mirror(original_root, 2)

The output will be a binary tree with ‘2’ as its root.

Through `reroot_mirror()`

, we recursively search for the new root value. Once found, we perform the necessary swaps to make the new root the topmost node while mirroring the nodes along the path. This preserves the binary tree’s structural integrity.

## Method 4: Path Reversal

The path reversal method changes the root by keeping track of the path from the old root to the new root and then reversing the direction of the pointers along this path, thus promoting the new root to the top of the binary tree without creating new nodes.

Here’s an example:

def reroot_path_reverse(old_root, new_root_value): path = [] node = old_root while node.value != new_root_value: path.append(node) if new_root_value < node.value: node = node.left else: node = node.right path.append(node) for i in range(len(path) - 1, 0, -1): path[i].left, path[i].right = path[i].right, path[i - 1] path[0].left = path[0].right = None return path[-1] # Example Usage original_root = TreeNode(1, TreeNode(2), TreeNode(3)) new_tree_root = reroot_path_reverse(original_root, 2)

The output is a binary tree with the node ‘2’ as its new root.

The function `reroot_path_reverse()`

stores the nodes along the path to the new root in an array. Upon reaching the new root, it starts from the end of the array, reversing the order of the children until the new root is at the start of the path, with no children pointing back.

## Bonus One-Liner Method 5: Simple Swap

If the tree structure allows, a one-line solution may be used to swap the root with one of its direct children. This method is only applicable in cases where such a direct swap is structurally valid for the binary tree without violating its properties.

Here’s an example:

# Assumption: new_root is a direct child of old_root new_tree_root = old_root.left if old_root.left.value == new_root_value else old_root.right

Output: Either left or right child of the original root becomes the new root.

This succinct line of code assumes that the new root is a direct child of the old root, and performs a simple assignment based on the value comparison.

## Summary/Discussion

**Method 1: Recursive Re-rooting.**Preserves tree structure and nodes. Optimal for small to medium-sized trees. May encounter stack overflow with very deep trees.**Method 2: Iterative Tree Re-rooting.**Eliminates recursion overhead. Suitable for large trees. Less intuitive than the recursive approach.**Method 3: Mirror and Adjust.**A more complex but versatile approach. Preserves node integrity. Potentially more computationally expensive, especially for deeper trees.**Method 4: Path Reversal.**Works well on balanced trees. Itβs efficient and straightforward when new root is near the old root. Not suitable for unbalanced trees where the path is long.**Bonus Method 5: Simple Swap.**The quickest method when applicable. Only works when the new root is a direct child of the old root; thus, it is the least flexible method.