What You See Looking at the Tree From the Right

Medium20–25 min

Topics

Binary TreeBFSDFSTree Views

Companies

AmazonFacebookMicrosoftGoogleAdobe

You are given the root of a binary tree. Picture yourself standing on its right-hand side, looking towards the tree. At every level you can see only the rightmost node of that level; anything to its left is hidden. Return the values of the visible nodes ordered from the top level to the bottom level.

You could gather all the values of each level and keep the last one, or walk level by level with a queue and note only the last node of every level.

Test Case 1:

Input:root = [12, 5, 18, 3, 8, null, 21, 1]

Output:[12, 18, 21, 1]

Explanation:Level 0: 12. Level 1: 5 and 18 — 18 is rightmost. Level 2: 3, 8, 21 — 21 is rightmost. Level 3: only 1, which belongs to the LEFT part of the tree but is still the rightmost node on its level, so it is visible.

Test Case 2:

Input:root = [7, 3]

Output:[7, 3]

Explanation:A single left child is the only node on its level, so it is visible.

Test Case 3:

Input:root = []

Output:[]

Explanation:Nothing to see.

Constraints

◆0 ≤ number of nodes ≤ 100
◆−100 ≤ node.val ≤ 100
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆Imagine standing to the right of the tree. At each level you can see only the rightmost node of that level (nodes to its left are hidden behind it). Return those visible values from the top level to the bottom. An empty tree gives an empty list

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Gather Every Level With DFS, Keep the Last of Each

Brute

Recurse over the whole tree with the depth as a parameter, appending each node's value to a list for its depth (left subtree before right subtree, so the values in a list are in left-to-right order). When the walk is done, every list is one level, and the rightmost node of a level is simply the last item of its list. Collect those last items from the top level down. Correct, but it stores all n values only to throw most of them away: O(n) time and O(n) space.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public List<Integer> rightEdgeView(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        group(root, 0, levels);
        List<Integer> view = new ArrayList<>();
        for (List<Integer> level : levels) {
            view.add(level.get(level.size() - 1));
        }
        return view;
    }

    private void group(TreeNode node, int depth, List<List<Integer>> levels) {
        if (node == null) return;
        if (levels.size() == depth) levels.add(new ArrayList<>());
        levels.get(depth).add(node.val);
        group(node.left, depth + 1, levels);
        group(node.right, depth + 1, levels);
    }
}

Optimal — Level-by-Level, Record Only the Last Node of Each Level

Optimal

Traverse level by level with a queue. On each round the queue size is the number of nodes on the level; take that many nodes from the front, and when the node being processed is the last one (index size − 1), add its value to the answer. Children are queued as usual. Nothing but the answer is stored — the queue holds at most one or two levels — so it uses O(w) extra space instead of O(n), with O(n) time. (A depth-first walk that visits the right child first and records the first node seen at each new depth is another O(h)-space alternative.)