Leetcode 1666 Change the Root of a Binary Tree

Problem statement

https://leetcode.com/problems/change-the-root-of-a-binary-tree/

Solution

This is type of tree problems where you need to reconstruct tree following given rules. Usualy recursion (dfs) if useful. The idea is to traverse from root to leaf and do what we need on each step:

1. Create new connection between node and its child: we need to know which child to delete.
2. If we reached root, return node.
3. Finally we need to reconnect children and run function recursively.

Complexity

Time and space complexity is O(h).

Code

# borrowed code
class Solution:
    def flipBinaryTree(self, root, leaf):
        def dfs(node, child):
            p = node.parent
            node.parent = child
            if node.left == child: node.left = None
            if node.right == child: node.right = None
                
            if node == root:
                return node
            
            if node.left: node.right = node.left
            node.left = dfs(p, node)
            return node
        
        return dfs(leaf, None)