Changing the root of a binary tree

If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem: Change the Root of a Binary Tree - LeetCode

1666. Change the Root of a Binary Tree

Medium

Given the root of a binary tree and a leaf node, reroot the tree so that the leaf is the new root.

You can reroot the tree with the following steps for each node cur on the path starting from the leaf up to the root​​​ excluding the root:

1. If cur has a left child, then that child becomes cur's right child. Note that it is guaranteed that cur will have at most one child.
2. cur's original parent becomes cur's left child.

Return the new root of the rerooted tree.

Note: Ensure that your solution sets the Node.parent pointers correctly after rerooting or you will receive "Wrong Answer".

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• -109 <= Node.val <= 109
• All Node.val are unique.
• leaf exist in the tree.

Usually for problems like this it helps to get a sheet and start scribbling ideas. The idea is to write a function which takes a node (current) and its future parent and process that node. If the node is null, there is nothing else to be done. The process follows the rules specified by the problem. I also use the fact that all the nodes in the tree are unique. This allows me to do three important things:

1. Use this as a condition to stop when we reach the root

2. Reset the left and right node for the root (that must be done prior to #1)

3. Assign the right node to the left only when the left node has not be used yet

Code is not that straightforward, took me few debugging rounds to get it working. Raw scribbling sheet is also below. Hope you enjoy, cheers, ACC.

public Node FlipBinaryTree(Node root, Node leaf)
{
    if (root == null) return root;
    FlipBinaryTree(leaf, null, new Hashtable(), root.val);
    return leaf;
}

private void FlipBinaryTree(Node current, Node parent, Hashtable processed, int rootVal)
{
    if (current == null) return;
    Node temp = current.parent;
    current.parent = parent;
    if (current.val == rootVal)
    {
        if (current.left != null && processed.ContainsKey(current.left.val)) current.left = null;
        if (current.right != null && processed.ContainsKey(current.right.val)) current.right = null;
        return;
    }
    if (current.left != null && !processed.ContainsKey(current.left.val)) current.right = current.left;
    current.left = temp;
    processed.Add(current.val, true);
    FlipBinaryTree(temp, current, processed, rootVal);
}