Pre-Order and Post-Order Traversals in the same Problem II

An interesting problem (which I guarantee you'll never see in real life) to turn a tree upside down (yeah, guaranteed).

Three steps taken here:

1. A pre-order approach to find the new root (just a loop going thru the left nodes)

2. A post-order approach to turn every node upside down using the given rules

3. Make the original root a leaf node

Code is down below, cheers, ACC.

Binary Tree Upside Down - LeetCode

156. Binary Tree Upside Down

Medium

Given the root of a binary tree, turn the tree upside down and return the new root.

You can turn a binary tree upside down with the following steps:

1. The original left child becomes the new root.
2. The original root becomes the new right child.
3. The original right child becomes the new left child.

The mentioned steps are done level by level. It is guaranteed that every right node has a sibling (a left node with the same parent) and has no children.

 

Example 1:

Input: root = [1,2,3,4,5]
Output: [4,5,2,null,null,3,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

 

Constraints:

• The number of nodes in the tree will be in the range [0, 10].
• 1 <= Node.val <= 10
• Every right node in the tree has a sibling (a left node that shares the same parent).
• Every right node in the tree has no children.

public TreeNode UpsideDownBinaryTree(TreeNode root)
{
    if (root == null) return root;

    //Calculate new root (leftmost)
    TreeNode retVal = root;
    while (retVal.left != null) retVal = retVal.left;

    //Upside down all the other nodes
    UpsideDownBinaryTree(root, null);
        
    //Make the original root a leaf
    root.left = null;
    root.right = null;

    return retVal;
}

private void UpsideDownBinaryTree(TreeNode current, TreeNode parent)
{
    if (current == null) return;

    if (current.left != null)
        UpsideDownBinaryTree(current.left, current);

    if (parent != null)
    {
        current.right = parent;
        current.left = parent.right;
    }
}