Jobs

Interviews

Discussions

Change the Root of a Binary Tree

Medium

Asked by:

43 views

Topics:

TreesRecursion

Given the root of a binary tree and a node newRoot, change the root of the tree to be newRoot.

You are allowed to do the following operation on the tree:

Disconnect the parent node from one of its children.
Connect a node to be the new parent of another node.

Return the root of the rearranged tree.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], newRoot = 7
Output: [7,5,1,6,2,0,8,null,null,3,4,null,null,null,null,null,null]
Explanation: Each node in the diagram represents a node in the binary tree.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], newRoot = 6
Output: [6,5,1,3,2,0,8,null,null,7,4]

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
0 <= Node.val <= 10⁵
Each node has a unique value.

Try coding it in LeetCode

Change the Root of a Binary Tree

Medium

Asked by:

43 views

Topics:

TreesRecursion

Given the root of a binary tree and a node newRoot, change the root of the tree to be newRoot.

You are allowed to do the following operation on the tree:

Disconnect the parent node from one of its children.
Connect a node to be the new parent of another node.

Return the root of the rearranged tree.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], newRoot = 7
Output: [7,5,1,6,2,0,8,null,null,3,4,null,null,null,null,null,null]
Explanation: Each node in the diagram represents a node in the binary tree.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], newRoot = 6
Output: [6,5,1,3,2,0,8,null,null,7,4]

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
0 <= Node.val <= 10⁵
Each node has a unique value.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, and if so, what should I return?
Are the node values unique within the tree, or can there be duplicates?
Can I assume that the new root node is always present in the original tree?
Do I need to preserve the original tree structure, or is it acceptable to modify it destructively?
Can you provide an example of the desired output tree structure for a specific input and new root node?

Brute Force Solution

Approach

The goal is to rearrange a tree so a different node becomes the top node. The brute force method explores every possible tree arrangement to find the one where the desired node is at the top, without any clever tricks.

Here's how the algorithm would work step-by-step:

First, disconnect all the connections between nodes in the original tree. Now you just have a bunch of separate nodes.
Next, pick the node that we want to be the new root. This node will be the starting point for building our new tree.
Now, try every possible way to reconnect the other nodes to this new root. Think of it like trying every possible family tree structure.
For each of these possible tree structures, check if it's a valid binary tree. This means making sure each node has at most two children.
Also check if all the original nodes are included in the new tree structure.
Once we have found a valid binary tree that has our desired node at the root, we stop, because the brute force method returns the first valid arrangement it finds.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def change_root_brute_force(root, new_root_value):
    if not root:
        return None

    all_nodes = []
    node_map = {}

    def traverse(node):
        if node:
            all_nodes.append(node)
            node_map[node.value] = node
            traverse(node.left)
            traverse(node.right)

    traverse(root)

    # Disconnect all connections
    for node in all_nodes:
        node.left = None
        node.right = None

    import itertools

    for permutation in itertools.permutations(all_nodes):
        new_root = node_map.get(new_root_value)
        if not new_root:
            return None

        remaining_nodes = list(permutation)
        remaining_nodes.remove(new_root)
        
        # Try to build a valid binary tree
        if build_tree(new_root, remaining_nodes, node_map):
            
            all_nodes_present = True
            reconstructed_nodes = []
            
            def collect_nodes(node):
                if node:
                    reconstructed_nodes.append(node)
                    collect_nodes(node.left)
                    collect_nodes(node.right)
            
            collect_nodes(new_root)
            
            if len(reconstructed_nodes) != len(all_nodes):
                all_nodes_present = False

            present_values = [node.value for node in reconstructed_nodes]

            for original_node in all_nodes:
                if original_node.value not in present_values:
                    all_nodes_present = False
                    break

            if all_nodes_present:
                return new_root

    return None

def build_tree(root, remaining_nodes, node_map):
    # Base case: No more nodes to add
    if not remaining_nodes:
        return True

    # Attempt to add left and right children.
    available_nodes = remaining_nodes[:]
    
    for left_node in available_nodes:
        temp_remaining_nodes = remaining_nodes[:]
        temp_remaining_nodes.remove(left_node)

        root.left = left_node
        
        if build_tree(root, temp_remaining_nodes, node_map):
            return True

        root.left = None
        
    available_nodes = remaining_nodes[:]
    for right_node in available_nodes:
        temp_remaining_nodes = remaining_nodes[:]
        temp_remaining_nodes.remove(right_node)

        root.right = right_node

        if build_tree(root, temp_remaining_nodes, node_map):
            return True

        root.right = None
    # No valid arrangement found
    return False

Big(O) Analysis

Time Complexity

O(n! * n) – The algorithm explores all possible tree arrangements. For n nodes, there are n! (n factorial) ways to arrange them. For each arrangement, we need to check if it's a valid binary tree. Checking for binary tree validity and node inclusion takes O(n) time. Therefore, the total time complexity is O(n! * n), dominated by the generation and validation of all permutations.

Space Complexity

O(N!) – The brute force approach explores every possible tree arrangement. Step 3 considers every possible way to reconnect the nodes, implying generating all permutations of the nodes besides the new root. Storing each potential tree structure requires auxiliary space to represent the connections, which grows factorially with the number of nodes. Therefore, this leads to the need to store an amount of data equal to the number of possible permutations. Thus, the auxiliary space complexity is O(N!), where N is the number of nodes in the tree.

Optimal Solution

Approach

To change the root of a binary tree, we essentially need to reverse the direction of the pointers between nodes along the path from the new root to the original root. We achieve this by iteratively updating the parent-child relationships until the desired root becomes the top-most node.

Here's how the algorithm would work step-by-step:

Start at the node you want to make the new root.
Remember the current node's parent and its right and left children.
Change the current node's left or right pointer to point towards its original parent.
Make the original parent's new child be the current node's former child.
Move up the tree from the current node to what was formerly its parent.
Repeat the process until you reach the original root. It will become a child of the new root.
Finally, the node you started with is now the root of the tree, and all parent-child relationships along the path have been reversed.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

def change_root(original_root, new_root):
    current_node = new_root
    previous_parent = None

    while current_node != original_root:
        # Store the original parent and children
        next_parent = current_node.parent
        left_child = current_node.left
        right_child = current_node.right

        # Reverse the pointer to the parent
        if next_parent:
            if next_parent.left == current_node:
                current_node.left = next_parent
            else:
                current_node.right = next_parent
        else:
            if previous_parent:
                if current_node.left == previous_parent:
                    current_node.left = None
                else:
                    current_node.right = None

        # Update the parent's child pointer
        if previous_parent:
            if previous_parent.left == current_node:
                previous_parent.left = right_child
            else:
                previous_parent.right = right_child
            if right_child:
                right_child.parent = previous_parent

        # Set the new parent of the previous parent
        current_node.parent = previous_parent

        # Move to the next node
        previous_parent = current_node
        current_node = next_parent

    # Handle the original root
    if previous_parent:
        if previous_parent.left == current_node:
            previous_parent.left = current_node.right
        else:
            previous_parent.right = current_node.right
        if current_node.right:
            current_node.right.parent = previous_parent

    # The final step connects the original root to new root.
    current_node.parent = previous_parent
    if previous_parent.left == current_node:
        previous_parent.left = None
    else:
        previous_parent.right = None

    return new_root

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the path from the new root to the original root, reversing the parent-child relationships along the way. In the worst-case scenario, the path from the new root to the original root includes all nodes in the tree. Therefore, the number of nodes visited is proportional to n, where n is the number of nodes in the tree. Each node along this path is visited and updated once. Therefore, the total time complexity is O(n).

Space Complexity

O(1) – The algorithm iteratively updates parent-child relationships by storing a few node pointers: the current node's parent and its children. These temporary variables hold references to existing nodes, not copies, and their number remains constant regardless of the number of nodes (N) in the tree. Therefore, the auxiliary space used is independent of the input size. The space complexity is O(1), indicating constant extra space.

Edge Cases

Case	How to Handle
Null or Empty Tree	Return null immediately if the input tree is null or empty, as there is no root to change.
Target New Root is Null or Not in the Tree	Return the original tree (or null if original tree is null) if the target new root node is null or not present in the tree; otherwise, the transformation will fail.
Target New Root is Already the Current Root	Return the original tree as is if the specified new root is already the root of the tree.
Tree with only one node (the root)	If the tree has only one node and it's the new root, return the tree as is.
Skewed Tree (all nodes on one side)	The algorithm needs to handle potentially deep recursion stacks appropriately for highly skewed trees to avoid stack overflow errors, potentially requiring iterative solution.
Very Large Tree (memory constraints)	Consider an iterative approach to avoid stack overflow and potentially optimize memory usage during the tree rotation, although true in-place rotation could be complex.
Tree with duplicate values (finding the correct target)	If duplicate values exist, ensure the algorithm finds the specific intended node to become the new root, potentially using a node identifier along with value for comparison.
Integer overflow if storing node values (relevant if algorithm uses node values)	If node values are used in calculations (unlikely for root change but conceivable), be mindful of potential integer overflows and use appropriate data types or checks.

Null or Empty Tree

How to Handle:

Return null immediately if the input tree is null or empty, as there is no root to change.

Target New Root is Null or Not in the Tree

How to Handle:

Return the original tree (or null if original tree is null) if the target new root node is null or not present in the tree; otherwise, the transformation will fail.

Target New Root is Already the Current Root

How to Handle:

Return the original tree as is if the specified new root is already the root of the tree.

Tree with only one node (the root)

How to Handle:

If the tree has only one node and it's the new root, return the tree as is.

Skewed Tree (all nodes on one side)

How to Handle:

The algorithm needs to handle potentially deep recursion stacks appropriately for highly skewed trees to avoid stack overflow errors, potentially requiring iterative solution.

Very Large Tree (memory constraints)

How to Handle:

Consider an iterative approach to avoid stack overflow and potentially optimize memory usage during the tree rotation, although true in-place rotation could be complex.

Tree with duplicate values (finding the correct target)

How to Handle:

If duplicate values exist, ensure the algorithm finds the specific intended node to become the new root, potentially using a node identifier along with value for comparison.

Integer overflow if storing node values (relevant if algorithm uses node values)

How to Handle:

If node values are used in calculations (unlikely for root change but conceivable), be mindful of potential integer overflows and use appropriate data types or checks.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, and if so, what should I return?
Are the node values unique within the tree, or can there be duplicates?
Can I assume that the new root node is always present in the original tree?
Do I need to preserve the original tree structure, or is it acceptable to modify it destructively?
Can you provide an example of the desired output tree structure for a specific input and new root node?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, disconnect all the connections between nodes in the original tree. Now you just have a bunch of separate nodes.
Next, pick the node that we want to be the new root. This node will be the starting point for building our new tree.
Now, try every possible way to reconnect the other nodes to this new root. Think of it like trying every possible family tree structure.
For each of these possible tree structures, check if it's a valid binary tree. This means making sure each node has at most two children.
Also check if all the original nodes are included in the new tree structure.
Once we have found a valid binary tree that has our desired node at the root, we stop, because the brute force method returns the first valid arrangement it finds.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def change_root_brute_force(root, new_root_value):
    if not root:
        return None

    all_nodes = []
    node_map = {}

    def traverse(node):
        if node:
            all_nodes.append(node)
            node_map[node.value] = node
            traverse(node.left)
            traverse(node.right)

    traverse(root)

    # Disconnect all connections
    for node in all_nodes:
        node.left = None
        node.right = None

    import itertools

    for permutation in itertools.permutations(all_nodes):
        new_root = node_map.get(new_root_value)
        if not new_root:
            return None

        remaining_nodes = list(permutation)
        remaining_nodes.remove(new_root)
        
        # Try to build a valid binary tree
        if build_tree(new_root, remaining_nodes, node_map):
            
            all_nodes_present = True
            reconstructed_nodes = []
            
            def collect_nodes(node):
                if node:
                    reconstructed_nodes.append(node)
                    collect_nodes(node.left)
                    collect_nodes(node.right)
            
            collect_nodes(new_root)
            
            if len(reconstructed_nodes) != len(all_nodes):
                all_nodes_present = False

            present_values = [node.value for node in reconstructed_nodes]

            for original_node in all_nodes:
                if original_node.value not in present_values:
                    all_nodes_present = False
                    break

            if all_nodes_present:
                return new_root

    return None

def build_tree(root, remaining_nodes, node_map):
    # Base case: No more nodes to add
    if not remaining_nodes:
        return True

    # Attempt to add left and right children.
    available_nodes = remaining_nodes[:]
    
    for left_node in available_nodes:
        temp_remaining_nodes = remaining_nodes[:]
        temp_remaining_nodes.remove(left_node)

        root.left = left_node
        
        if build_tree(root, temp_remaining_nodes, node_map):
            return True

        root.left = None
        
    available_nodes = remaining_nodes[:]
    for right_node in available_nodes:
        temp_remaining_nodes = remaining_nodes[:]
        temp_remaining_nodes.remove(right_node)

        root.right = right_node

        if build_tree(root, temp_remaining_nodes, node_map):
            return True

        root.right = None
    # No valid arrangement found
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the node you want to make the new root.
Remember the current node's parent and its right and left children.
Change the current node's left or right pointer to point towards its original parent.
Make the original parent's new child be the current node's former child.
Move up the tree from the current node to what was formerly its parent.
Repeat the process until you reach the original root. It will become a child of the new root.
Finally, the node you started with is now the root of the tree, and all parent-child relationships along the path have been reversed.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

def change_root(original_root, new_root):
    current_node = new_root
    previous_parent = None

    while current_node != original_root:
        # Store the original parent and children
        next_parent = current_node.parent
        left_child = current_node.left
        right_child = current_node.right

        # Reverse the pointer to the parent
        if next_parent:
            if next_parent.left == current_node:
                current_node.left = next_parent
            else:
                current_node.right = next_parent
        else:
            if previous_parent:
                if current_node.left == previous_parent:
                    current_node.left = None
                else:
                    current_node.right = None

        # Update the parent's child pointer
        if previous_parent:
            if previous_parent.left == current_node:
                previous_parent.left = right_child
            else:
                previous_parent.right = right_child
            if right_child:
                right_child.parent = previous_parent

        # Set the new parent of the previous parent
        current_node.parent = previous_parent

        # Move to the next node
        previous_parent = current_node
        current_node = next_parent

    # Handle the original root
    if previous_parent:
        if previous_parent.left == current_node:
            previous_parent.left = current_node.right
        else:
            previous_parent.right = current_node.right
        if current_node.right:
            current_node.right.parent = previous_parent

    # The final step connects the original root to new root.
    current_node.parent = previous_parent
    if previous_parent.left == current_node:
        previous_parent.left = None
    else:
        previous_parent.right = None

    return new_root

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Tree	Return null immediately if the input tree is null or empty, as there is no root to change.
Target New Root is Null or Not in the Tree	Return the original tree (or null if original tree is null) if the target new root node is null or not present in the tree; otherwise, the transformation will fail.
Target New Root is Already the Current Root	Return the original tree as is if the specified new root is already the root of the tree.
Tree with only one node (the root)	If the tree has only one node and it's the new root, return the tree as is.
Skewed Tree (all nodes on one side)	The algorithm needs to handle potentially deep recursion stacks appropriately for highly skewed trees to avoid stack overflow errors, potentially requiring iterative solution.
Very Large Tree (memory constraints)	Consider an iterative approach to avoid stack overflow and potentially optimize memory usage during the tree rotation, although true in-place rotation could be complex.
Tree with duplicate values (finding the correct target)	If duplicate values exist, ensure the algorithm finds the specific intended node to become the new root, potentially using a node identifier along with value for comparison.
Integer overflow if storing node values (relevant if algorithm uses node values)	If node values are used in calculations (unlikely for root change but conceivable), be mindful of potential integer overflows and use appropriate data types or checks.

Null or Empty Tree

How to Handle:

Return null immediately if the input tree is null or empty, as there is no root to change.

Target New Root is Null or Not in the Tree

How to Handle:

Return the original tree (or null if original tree is null) if the target new root node is null or not present in the tree; otherwise, the transformation will fail.

Target New Root is Already the Current Root

How to Handle:

Return the original tree as is if the specified new root is already the root of the tree.

Tree with only one node (the root)

How to Handle:

If the tree has only one node and it's the new root, return the tree as is.

Skewed Tree (all nodes on one side)

How to Handle:

The algorithm needs to handle potentially deep recursion stacks appropriately for highly skewed trees to avoid stack overflow errors, potentially requiring iterative solution.

Very Large Tree (memory constraints)

How to Handle:

Consider an iterative approach to avoid stack overflow and potentially optimize memory usage during the tree rotation, although true in-place rotation could be complex.

Tree with duplicate values (finding the correct target)

How to Handle:

If duplicate values exist, ensure the algorithm finds the specific intended node to become the new root, potentially using a node identifier along with value for comparison.

Integer overflow if storing node values (relevant if algorithm uses node values)

How to Handle:

If node values are used in calculations (unlikely for root change but conceivable), be mindful of potential integer overflows and use appropriate data types or checks.