Binary Tree Upside Down Python Solution

LeetCode 156, Medium. Topics: Tree, Depth-First Search, Binary Tree. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 14 parametrized pytest cases, and a playground notebook:

lcpy gen -n 156   # by problem number
lcpy gen -s binary_tree_upside_down   # by problem name

Problem

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:

The original left child becomes the new root.
The original root becomes the new right child.
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 that shares the same parent) and has no children.

Examples

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

Input: root = []
Output: []

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

Constraints

The number of nodes in the tree is 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

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(1)
    def upside_down_binary_tree(self, root: TreeNode[int] | None) -> TreeNode[int] | None:
        curr = root
        prev: TreeNode[int] | None = None
        prev_right: TreeNode[int] | None = None
        while curr is not None:
            next_curr = curr.left
            orig_right = curr.right
            curr.left = prev_right
            curr.right = prev
            prev_right = orig_right
            prev = curr
            curr = next_curr
        return prev

Complexity

Time	Space
O(n)	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Binary Tree Upside Down Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags