Invert Binary Tree

Q: What is the time complexity of inverting a binary tree?

Each node is visited once, so the time is O(n) . A recursive solution uses O(h) stack space for a tree of depth h , and a queue-based one uses O(w) for the widest level. In this array version the answer itself is a new array, which adds O(n) .

EasyTree traversal

+10

You get a binary tree stored in the array tree in level order. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries.

Invert the tree: swap the left and right child of every node, so the whole tree becomes its mirror image. Return the inverted tree in the same form, with no -1 entries at the end.

Function

invertTree(tree: integer-array) → integer-array

treeinteger-array: the binary tree in level order, with -1 for an empty spot
Returnsinteger-array: the mirrored tree in level order, without trailing -1 entries

Constraints

1 ≤ tree.length ≤ 16383
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 1000.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.

Examples

Input: tree = [5, 3, 8, 1, 4, -1, 9]
Output: [5, 8, 3, 9, -1, 4, 1]
Explanation: The root's children 3 and 8 trade places. Under them, the 1 and 4 below 3 come back as 4 and 1, and 8, which had only a right child 9, now has it on its left.

Input: tree = [2, 7, -1, 6]
Output: [2, -1, 7, -1, -1, -1, 6]
Explanation: The chain 2, 7, 6 leans left and its mirror leans right. The 7 moves from index 1 to index 2 and the 6 from index 3 to index 6, so the answer is longer than the input, with -1 in every empty spot before the last node.

Input: tree = [1, -1, -1]
Output: [1]
Explanation: A single node is its own mirror. The two -1 entries are padding, and the answer drops every -1 at the end.

+14 hidden tests on Submit

Follow-up

How would you check whether a tree is its own mirror, using the same index pairs but without building the inverted copy?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Mirroring a tree means every node swaps its left and right subtree, all the way down. With node objects that is one swap per node. In this array form a node's place is its index, so swapping two subtrees means moving every node inside them. The way through is to build the answer in a new array and copy each node straight to its mirrored index, carrying pairs of indexes through a traversal: where the node is now, and where it goes.

Recursion that places each node at its mirrored index

Intuition

First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2. A child is real only if its index is inside the array and the value there is not -1. In [5, 3, 8, 1, 4, -1, 9] the root 5 has 3 and 8 at indexes 1 and 2, and the 8 at index 2 has an empty left spot at 5 and the 9 at 6.

Now the mirror. The root stays at index 0. A node's left subtree becomes the right subtree of its mirrored copy, and its right subtree becomes the left one. So if the node at index src lands at index dst in the answer, its left child lands at 2*dst+2 and its right child at 2*dst+1. Write place(src, dst): copy the value, then call place(2*src+1, 2*dst+2) and place(2*src+2, 2*dst+1). An empty spot returns at once. In the first example the 3 at index 1 lands at 2, so its left child 1 lands at 6 and its right child 4 at 5.

A node never changes level, so its mirrored index stays inside the same level as its old one. Round the length up to whole levels (1, 3, 7, 15, ...), fill that many slots with -1, and trim the trailing -1 entries at the end. In the second example the length 4 rounds up to 7, which leaves room for the 6 at index 6.

Every node is placed once and the output is filled and trimmed once, O(n) time for an array of length n. The output takes O(n) memory and the call stack O(h), at most 14 frames here, which is what makes recursion safe in this problem.

Algorithm

Round the length up to size = 2^k - 1 and fill an output of that size with -1.
Write place(src, dst): if src is past the end or tree[src] is -1, return.
Otherwise set out[dst] = tree[src], then call place(2*src+1, 2*dst+2) and place(2*src+2, 2*dst+1).
Call place(0, 0), drop the trailing -1 entries and return the output.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

    place(0, 0)
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Breadth-first search with a queue of index pairs

Intuition

The same pairs work without recursion. Put (0, 0) in a queue: the root, and the spot it goes to. Take a pair (src, dst) from the front, copy tree[src] to out[dst], and queue each real child with its swapped destination: the left child 2*src+1 with 2*dst+2, the right child 2*src+2 with 2*dst+1.

This is the classic iterative inversion. With node objects you take a node from the queue, swap its two children, and queue them. Here the swap is written into the destination index instead, because the array cannot swap two whole subtrees in one step. Every real node enters the queue once, carrying the exact spot it belongs to, so the output ends up holding every node in its mirrored place. In the first example the pairs come out as (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

The time is O(n). The queue holds at most one level and a bit, O(w) for the widest level w, on top of the O(n) output. There is no call stack to overflow, so this version carries over unchanged to deep pointer-based trees.

Algorithm

Round the length up to whole levels and fill an output of that size with -1.
Put the pair (0, 0) in a queue.
Take a pair (src, dst) from the front and set out[dst] = tree[src].
Queue (2*src+1, 2*dst+2) and (2*src+2, 2*dst+1) for each child that is inside the array and not -1.
When the queue is empty, drop the trailing -1 entries and return the output.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Pitfalls and edge cases

The mirror itself is short to describe. The bugs come from the array: its size, its end, and what a swap of two entries really moves.

Swapping tree[2*i+1] and tree[2*i+2] in place. That swaps two values but not the subtrees under them. Swapping indexes 1 and 2 in the first example leaves 1 and 4 hanging under the 8.
Making the output as long as the input. A mirrored node can land past the input's last index, as the 6 does in the second example. Size the output to whole levels.
Forgetting to trim. The answer has no -1 at the end, both for padded inputs and for trees whose mirror ends earlier than the input did.
Reversing the whole array. That mixes the levels: the last leaf would become the root.
Skipping the bounds check. A child index can be past the end of the input, because the array may stop right after the last node.
Mixing up the offset in Lua and R, where arrays start at 1. Keep the indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions4

What does it mean to invert a binary tree?

Inverting a binary tree turns it into its mirror image: at every node the left and right subtrees trade places. The root stays where it is, the leftmost leaf becomes the rightmost, and a left chain becomes a right chain. Inverting twice gives the original tree back.

What is the time complexity of inverting a binary tree?

Each node is visited once, so the time is O(n). A recursive solution uses O(h) stack space for a tree of depth h, and a queue-based one uses O(w) for the widest level. In this array version the answer itself is a new array, which adds O(n).

How do you invert a binary tree without recursion?

Use a queue or a stack. Start with the root, and each time you take a node out, swap its left and right child and put the children in. Every node gets its swap once, in whatever order the structure hands them out. In the array form you queue pairs of indexes instead and write each node straight to its mirrored spot.

Why does inverting a binary tree reverse each level?

Mirroring flips left and right everywhere, so the nodes on each level appear in the opposite order. In level order storage that means each level's slice of the array is reversed: the slice [1, 4, -1, 9] of the first example comes back as [9, -1, 4, 1]. Reversing each level, after padding the last one with -1, is a third O(n) answer that only works for this array layout.

Python

def invertTree(tree):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

tree = [5, 3, 8, 1, 4, -1, 9]

Expected

[5, 8, 3, 9, -1, 4, 1]