Left View of Binary Tree

Q: What is the time and space complexity of the left view?

Both solutions look at every node once, so the time is O(n) . The breadth-first queue holds a whole level, about half the nodes of a full tree. The left-first walk holds one call per level, O(h) for h levels.

EasyTree traversal Queue

+10

You get a binary tree as the array root in heap order: the root is at index 0, the children of index i are at 2*i+1 (left) and 2*i+2 (right), and -1 marks an empty spot. The array may end with extra -1 entries.

Stand to the left of the tree. On every level you see one node, the leftmost; the rest of the level hides behind it. Return the values you see, from the top level down.

Function

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

rootinteger-array: the tree in heap order, with -1 for an empty spot
Returnsinteger-array: the leftmost 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 = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Output: [3, 8, 6, 1]
Explanation: 8 is a leaf, so the third and fourth levels hold only 6 (index 6) and 1 (index 13), both under the right child 5. You see them anyway: [3, 8, 6, 1].

Input: root = [10, -1, -1]
Output: [10]
Explanation: Indexes 1 and 2 hold -1, so 10 has no children and the view is the root alone.

Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1, 2, 4]
Explanation: A full tree of three levels. The leftmost spots of the levels are indexes 0, 1 and 3, which hold 1, 2 and 4.

Follow-up

Level d fills indexes 2^d-1 to 2^(d+1)-2. Can you build the view by scanning those ranges, with no queue or recursion? What does that cost on a padded array?

Solution

Following left children from the root fails when the left subtree is shorter: in the first example the lower levels are seen through the right subtree. You want the first node of every level. Breadth-first search hands you each level left to right; a depth-first walk that goes left first meets each level's leftmost node first.

Breadth-first, first node of each level

Intuition

A queue processed in rounds gives you the levels one at a time. At the start of a round the queue holds exactly one level, left to right, because every child added during the round lands behind it. Take out that many indexes, queue each one's children left first, and keep the first value.

In the first example the rounds are [3], [8, 5], [6] and [1], and they keep 3, 8, 6 and 1. The 8 adds nothing, because its child spots 3 and 4 hold -1.

Each node enters and leaves the queue once: O(n) time. The queue holds a whole level, up to 8192 indexes on a full tree of 14 levels.

Algorithm

Start a queue holding index 0, and an empty answer.
While the queue is not empty, let s be its size and remove s indexes. Append the value of the first one.
For each removed index i, queue 2i+1, then 2i+2, skipping indexes past the end and entries equal to -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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, left child first

Intuition

Walk depth-first, the left subtree before the right, and pass each node's depth. The first node the walk reaches at depth d is the leftmost on level d. Take the leftmost node x of a level and any node y to its right: at the last node their paths share, x goes left and y right, and the walk finishes the left branch before it turns right.

The walk goes down one level at a time, so when it first reaches depth d the answer holds exactly d values. Record a node when d equals the answer's length; no set of seen depths is needed.

Each node is visited once, O(n) time, and memory holds one call per level, at most 14 here. The R version keeps its own stack and pushes the right child before the left.

Algorithm

Create an empty answer and call visit(0, 0).
In visit(i, d), return at once if i is outside the array or root[i] is -1.
If d equals the answer's length, the walk has reached level d for the first time: append root[i].
Call visit(2i+1, d+1), then visit(2i+2, d+1).
Return the answer once the first call finishes.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Pitfalls and edge cases

Following only left children from the root. In the first example that stops at 8 and misses 6 and 1.
Reading the first slot of each level, root[2^d-1]. In the first example the third level's first slot, index 3, holds -1, while its only node sits at index 6.
Visiting the right child first in the depth-first walk. The first node met on each level is then the rightmost.
Reading a child without a bounds check. The 1 at index 13 has child spots 27 and 28, past the end of the 14-entry array.

Frequently asked questions3

Is the left view the same as the left boundary of a tree?

No. The left boundary is a path: it starts at the root's left child, goes left when it can, else right, and stops before a leaf. The left view takes one node per level from any branch. In the first example the boundary is empty, since 8 is a leaf, but the view shows 8, 6 and 1.

What is the time and space complexity of the left view?

Both solutions look at every node once, so the time is O(n). The breadth-first queue holds a whole level, about half the nodes of a full tree. The left-first walk holds one call per level, O(h) for h levels.

How do you change the solution to get the right view?

In the breadth-first version, keep the last value of each round instead of the first. In the depth-first version, visit the right child before the left; the first node the walk reaches on each level is then the rightmost.

def leftView(root):
    # Write code here

Test #1

Test #2

Test #3

Argument

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Expected Output

[3, 8, 6, 1]