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) . Recursion uses O(h) stack space for a tree of depth h , and a queue uses O(w) for the widest level. In this array version the answer 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, so its mirror leans right: 7 moves from index 1 to 2 and 6 from 3 to 6. The answer is longer than the input.

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.

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 swaps the left and right subtree of every node. Here a node's place is its index, so swapping two subtrees moves every node inside them. Build the answer in a new array instead, carrying a pair of indexes through a traversal: where a node is, and the mirrored spot where it goes.

Recursion that places each node at its mirrored index

Intuition

The root stays at index 0. A node's left subtree becomes the right subtree of its mirrored copy, so if the node at src lands at dst, its left child lands at 2*dst+2 and its right child at 2*dst+1. That gives place(src, dst), which copies one value and recurses on both children with their swapped destinations. In the first example the 3 at index 1 lands at 2, so its children 1 and 4 land at 6 and 5.

A node never changes level, but its mirrored index can land past the end of the input. Size the output to whole levels (1, 3, 7, 15, ...): in the second example length 4 becomes 7, room for the 6 at index 6. Each node is placed once, so the time is O(n), with an O(n) output and a call stack of at most 14 frames.

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 with a queue. Start with (0, 0); each pair you take out copies one value and queues each real child with its swapped destination. The swap is written into the destination index, because the array cannot swap two subtrees in one step. Every real node enters the queue once, carrying the spot it belongs to.

The time is O(n), and the queue holds O(w) pairs for the widest level w. There is no call stack to overflow.

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

Swapping tree[2*i+1] and tree[2*i+2] in place. That swaps two values, not their subtrees: in the first example 1 and 4 stay under the 8.
Making the output as long as the input. The 6 in the second example lands past the input's last index.
Forgetting to trim the trailing -1 entries, both for padded inputs and for mirrors that end earlier than the input.
In Lua and R, forgetting that arrays start at 1. Keep indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions3

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 put 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). Recursion uses O(h) stack space for a tree of depth h, and a queue uses O(w) for the widest level. In this array version the answer is a new array, which adds O(n).

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 each level's slice is reversed: the slice [1, 4, -1, 9] comes back as [9, -1, 4, 1]. Reversing each level, after padding the last one with -1, is a third O(n) answer for this layout.

def invertTree(tree):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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