Binary Tree Right Side View

Q: What is the time and space complexity of Binary Tree Right Side View?

The time is O(n) for n nodes, and no solution can skip nodes, since a level's rightmost node may hang anywhere. The space is O(w) for the queue, where w is the widest level, or O(h) for the right-first walk on a tree of h levels.

MediumTree traversal Queue

+10

The array root holds a binary tree. 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 extra -1 entries may trail at the end.

Look at the tree from its right side. Each level shows you exactly one node, the one furthest right, and blocks the rest. List those values from the root's level down to the deepest one.

Function

rightSideView(root: integer-array) → integer-array

rootinteger-array: the tree in heap order, with -1 for an empty spot
Returnsinteger-array: the rightmost value of every level, top level first

Constraints

1 ≤ root.length ≤ 32767
Each root[i] is -1 or a value with 0 ≤ root[i] ≤ 10⁴.
The node values are distinct.
root[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 tree has at most 14 levels.

Examples

Input: root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Output: [5, 9, 1, 3]
Explanation: From the right you see 5, 9 and 1 (index 6). The fourth level holds only 3, at index 8 under 7 in the left subtree. Nothing on the right reaches that deep, so 3 is visible.

Input: root = [6, 0, -1, 8, -1, -1, -1]
Output: [6, 0, 8]
Explanation: The tree is a chain of left children: 6, 0, 8. Each level holds one node, so you see all three, although none of them is a right child.

Input: root = [42]
Output: [42]
Explanation: An array of length 1: the root 42 has no child spots at all, and the view is that one value.

Follow-up

How would you get the right side view of a tree in which every node can have any number of children, stored as a list from left to right?

Hints

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

0 of 3 opened

Solution

You see the rightmost node of every level, and it need not be a right child: the last value of example 1 sits in the left subtree. A breadth-first search makes that node the last of each round; a depth-first walk that goes right first meets it before any other node on its level.

Breadth-first, last node of each level

Intuition

Process the tree one level per round. When a round starts, the queue holds exactly one level from left to right, so the last index you dequeue in the round is that level's rightmost node, and its value goes into the answer.

In example 1 the rounds are [5], [2, 9], [7, 4, 1] and [3], and their last entries give 5, 9, 1, 3. The level decides, not the side: 3 hangs in the left subtree, but it is alone on its level.

Every index is enqueued and dequeued once, so the time is O(n). The queue grows to the widest level, O(n) in the worst case.

Algorithm

Queue the root's index 0.
Start a round by saving the queue's length s.
Dequeue s indexes. For each index i, enqueue 2i+1 and then 2i+2 if they are below the array's length and not -1.
Append the value of the last index dequeued in the round.
Repeat until the queue is empty, then return the answer.

from collections import deque


def rightSideView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == size - 1:
                view.append(root[i])  # the last node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

Depth-first, right child first

Intuition

Walk depth-first, trying the right child before the left, and carry the depth, 0 at the root. The first time the walk reaches depth d, the answer holds exactly d values. Append the node's value then and ignore every later node on that level.

That first node is the rightmost one: wherever two paths to a level part ways, the walk follows the right branch to the bottom before it backs up into the left one. On example 1 the walk visits 5, 9, 1, 2, 4, 7, 3: it skips 2, 4 and 7, whose depths already have a value, and appends 3.

Each node is visited once, O(n) time, with one call per level on the stack, 14 at most.

Algorithm

Start with an empty answer and the root at depth 0.
Skip an index that is past the end of the array or holds -1.
When the answer's length equals the depth, append the value: the walk has reached a new level, and it reached it from the right.
Recurse into the right child 2i+2 first, then the left child 2i+1, each one level deeper.
Return the answer.

def rightSideView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

Pitfalls and edge cases

Following only right children from the root. Example 1 then gives [5, 9, 1] and misses 3; example 2 gives [6].
Reading the last slot of each level, root[2^(d+1)-2]. In example 2 index 6 holds -1; the visible node is 8 at index 3.
Skipping the length check on a child spot. In example 1, 3 is the last entry, so its child spots 17 and 18 do not exist.
Queueing the right child first while keeping the last node of each round. That collects the left view, [5, 2, 7, 3].
Letting later nodes overwrite earlier ones in the right-first walk, which also yields the left view.

Frequently asked questions3

What is the time and space complexity of Binary Tree Right Side View?

The time is O(n) for n nodes, and no solution can skip nodes, since a level's rightmost node may hang anywhere. The space is O(w) for the queue, where w is the widest level, or O(h) for the right-first walk on a tree of h levels.

Can a left-first depth-first search solve it?

Yes, if you overwrite instead of keeping the first value. A left-first walk meets each level's nodes from left to right, so store every node's value at its depth and let later nodes replace earlier ones. Each depth ends with its rightmost value. It is still O(n), but it writes once per node.

Should I use breadth-first or depth-first search here?

Both are linear. Breadth-first follows the definition, one level per round. Depth-first keeps only the current path, which saves memory on a wide tree, and its recursive form is a few lines shorter.

def rightSideView(root):
    # Write code here

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Expected Output

[5, 9, 1, 3]