Practice/LinkedIn/Leetcode 156. Binary Tree Upside Down

Leetcode 156. Binary Tree Upside Down

CodingOptional

Problem

Given a binary tree where every node has either zero or two children, and every left child has either zero or two children as well, transform the tree by inverting it along its left spine.

The transformation follows these rules:

• The leftmost node in the original tree becomes the root of the new tree
• Each parent node becomes the right child of its former left child
• Each right sibling becomes the left child of its former parent's new position

The original tree has a special structure: it only grows along the left spine, with each node potentially having a right child as well. Your task is to rearrange the pointers to flip this structure upside down.

Requirements

1. Implement an in-place solution that modifies the tree structure
2. The leftmost leaf node should become the new root
3. Along the left spine, each parent becomes the right child of its original left child
4. Each right child in the original tree becomes the left child in the inverted position
5. Return the new root of the transformed tree

Constraints

• The number of nodes in the tree is in the range [0, 1000]
• Node values are between -1000 and 1000
• The input tree follows the special structure described above
• Optimize for O(n) time complexity and O(1) or O(h) space complexity where h is the height

Examples

Example 1:

` Input: root = [1,2,3,4,5] Original Tree: 1 /
2 3 /
4 5

Output: [4,5,2,null,null,3,1] Transformed Tree: 4 /
5 2 /
3 1

Explanation: Node 4 (leftmost) becomes the root. Node 2 becomes 4's right child, node 5 becomes 2's left child, node 1 becomes 2's right child, and node 3 becomes 1's left child. `

Example 2:

` Input: root = [1,2] Original Tree: 1 / 2

Output: [2,null,1] Transformed Tree: 2
1

Explanation: With only two nodes on the left spine, node 2 becomes root and node 1 becomes its right child. `

Example 3:

` Input: root = [1]

Output: [1]

Explanation: A single node tree remains unchanged. `