Binary Tree Right Side View

1. Define the problem

Imagine standing to the right of a binary tree and looking at it. Return the values of the nodes you can see, ordered from top to bottom . In other words, return the last node of every level . A node hides every node behind it on the same level, so exactly one node per level is visible. The tree arrives as a level-order array such as [1, 2, 3, null, 5, null, 4], with null for a missing child. Your function builds the tree and returns a plain array of numbers.

Constraints

The number of nodes is between 0 and 100
-100 ≤ node value ≤ 100
Input is a level-order array with null for a missing child
Return an array of numbers, top level first

Example

Inputvalues = [1, 2, 3, null, 5, null, 4]

Output[1, 3, 4]

Explanation Level 0 holds only 1. Level 1 holds 2 and 3, and 3 is further right, so 3 is visible. Level 2 holds 5 and 4, and 4 is further right, so 4 is visible. The view from the right is [1, 3, 4].

2. Know the words first

In plain terms

Level: All the nodes that sit the same number of steps below the root. The root alone is level 0, its children are level 1, and so on.
Breadth-first search: Walking a tree one whole level at a time instead of diving down one branch first. You hold the current level in a list, read it, then build the list for the next level.
Queue: A waiting line where things leave in the order they arrived. Level-by-level walks use one so that nodes are visited in the order they were discovered.

3. Visualize the solution

One cell per level of the tree, holding the node visible from the right

lvl 0—

lvl 1—

lvl 2—

lvl 3—

Statusinit

The tree is built and the current level holds only the root.

What happens in this step

values = [1, 2, 3, null, 5, null, 4]

level = [1]
view = []

No level has been read yet.

Step 1 of 6

Steps to visualize

Each cell stands for one level of the tree, from the root level on the left.
Work level by level: read the whole current level, then build the next one.
The visible node is simply the last node in the current level list.
When the next level comes out empty, the tree is finished.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per level of the tree, holding the node visible from the right

lvl 0—

lvl 1—

lvl 2—

lvl 3—

Statusinit

The tree is built and the current level holds only the root.

What happens in this step

values = [1, 2, 3, null, 5, null, 4]

level = [1]
view = []

No level has been read yet.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function rightSideView(values) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  const root = buildTree(values);
  const view = [];

  if (root === null) {
    return view;
  }

  let level = [root];

  while (level.length > 0) {
    view.push(level[level.length - 1].val);

    const next = [];

    for (const node of level) {
      if (node.left !== null) {
        next.push(node.left);
      }

      if (node.right !== null) {
        next.push(node.right);
      }
    }

    level = next;
  }

  return view;
}

Time: O(n)
Space: O(w)

6. Test cases

Test cases

Input	Expected	Covers
`values = [1, 2, 3, null, 5, null, 4]`	`[1, 3, 4]`	example from the docstring
`values = [1, null, 3]`	`[1, 3]`	every node leans right
`values = []`	`[]`	empty tree, nothing is visible
`values = [1, 2]`	`[1, 2]`	a lone left child is still the last node on its level
`values = [1, 2, 3, 4]`	`[1, 3, 4]`	the deepest visible node hangs off the left branch
`values = [1, 2, 3, 4, 5, 6, 7]`	`[1, 3, 7]`	a complete tree with every slot filled

Binary Tree Right Side View