Invert Binary Tree

easyFREETreesBlind 75

Given the root of a binary tree (as a level-order array), invert it (mirror/flip left and right children recursively).

Output the level-order traversal of the inverted tree as space-separated values. A missing child that comes before a later node is written as null; trailing nulls are omitted, and an empty tree gives an empty string.

Example

Input

4,2,7,1,3,6,9

Output

4 7 2 9 6 3 1

Reasoning

Input: 4,2,7,1,3,6,9 lists the tree level by level, left to right. Level 0 is the root $4$ ; level 1 holds its children $2$ (left) and $7$ (right); level 2 holds $1, 3$ under $2$ and $6, 9$ under $7$ .
Mirroring reflects the tree across a vertical line through the root. Every node keeps its value and its depth, but its two subtrees trade sides, and the same reflection applies inside each subtree.
After the reflection the root $4$ has $7$ on the left and $2$ on the right. Under $7$ the children $6, 9$ become $9, 6$ ; under $2$ the children $1, 3$ become $3, 1$ .
Reading the mirrored tree level by level, left to right: $4$ , then $7, 2$ , then $9, 6, 3, 1$ , giving 4 7 2 9 6 3 1.
Notice that for a complete tree like this one, each level of the output is simply that level of the input reversed. A missing child in the middle of a level would show up as a null placeholder on the mirrored side.

Constraints

0 <= number of nodes <= 100
-100 <= Node.val <= 100

Learn this in

Depth First Search & TreesDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem involves working with a binary tree, which is a data structure in which each node has at most two children (i.e., left child and right child). In this case, we're given the root of the binary tree as a level-order array, which means the nodes are arranged in a specific order: the root node, followed by its children, then its grandchildren, and so on. To invert a binary tree means to mirror or flip its left and right children recursively. This operation requires a good understanding of recursion, which is a programming technique where a function calls itself repeatedly until it reaches a base case.

Understanding the structure of a binary tree is crucial to solving this problem. Each node in the tree has a value and references to its left and right children. When inverting the tree, we need to swap the left and right children of each node. This process needs to be repeated recursively for all nodes in the tree. The level-order traversal of a binary tree is also an important concept, as it involves visiting all nodes at a given level before moving on to the next level. In this case, we're asked to output the level-order traversal of the inverted tree as space-separated values.

The problem requires a combination of tree traversal and recursion to solve. Tree traversal involves visiting each node in the tree in a specific order, while recursion allows us to repeat this process for all nodes in the tree. By understanding how to traverse a binary tree and how to use recursion to repeat this process, we can develop an effective solution to invert the tree.

Algorithm/Approach

The general approach to solving this problem involves using a recursive algorithm to traverse the binary tree and invert its nodes. We can use a depth-first search (DFS) or breadth-first search (BFS) approach to traverse the tree, but in this case, a recursive DFS approach is more suitable. The algorithm will involve swapping the left and right children of each node and repeating this process recursively for all nodes in the tree.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a function to invert the binary tree recursively
Within the function, swap the left and right children of the current node
Recursively call the function on the left and right children of the current node
Use a level-order traversal to output the values of the inverted tree as space-separated values
Start the traversal from the root node and visit all nodes at each level before moving on to the next level

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to handle the base case for recursion (i.e., when the current node is null)
Not properly swapping the left and right children of each node
Not using recursion correctly to repeat the process for all nodes in the tree
Not implementing the level-order traversal correctly to output the values of the inverted tree

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of nodes in the binary tree, since we need to visit each node once to invert the tree. The expected space complexity is $O(n)$ as well, since in the worst case, the recursive call stack can go as high as the height of the tree, which is $n$ for an unbalanced tree. However, for a balanced tree, the space complexity would be $O(\log n)$ , where $\log n$ is the height of the tree.

solution.py

Python 3.13

Test results