Binary Tree Right Side View

NeetCode: Binary Tree Right Side View · LeetCode: 199. Binary Tree Right Side View · Difficulty: Medium

Imagine standing on the right side of a binary tree. Return the values you can see, from top to bottom.

Example

Text

Input:  [1, 2, 3, null, 5, null, 4]    Output: [1, 3, 4]

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: last node of every level

Do a level-order traversal and keep the last value of each level. ArrayDeque serves as the queue; queue.size() is read once before the inner loop, because the size changes as children are added.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size(); // the number of nodes on this level
            int last = 0;
            for (int k = 0; k < size; k++) {
                TreeNode node = queue.remove();
                last = node.val;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            view.add(last);
        }
        return view;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rightSideView(tree(1, 2, 3, null, 5, null, 4)));
        System.out.println(s.rightSideView(tree()));
    }
}

Output

[1, 3, 4]
[]

Time: O(n). Space: O(w), where w is the widest level.

Optimal: DFS visiting the right child first

Visiting the right child before the left, the first node reached at any depth is the rightmost one. So record a value only when its depth has not been seen yet: depth == view.size().

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private void dfs(TreeNode node, int depth, List<Integer> view) {
        if (node == null) {
            return;
        }
        if (depth == view.size()) {
            view.add(node.val);
        }
        dfs(node.right, depth + 1, view);
        dfs(node.left, depth + 1, view);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new ArrayList<>();
        dfs(root, 0, view);
        return view;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rightSideView(tree(1, 2, 3, null, 5, null, 4)));
        System.out.println(s.rightSideView(tree(1, 2)));
    }
}

Output

[1, 3, 4]
[1, 2]

Time: O(n). Space: O(h), compared with O(w) for BFS, so it uses less memory on wide, shallow trees. In [1, 2] the left child is visible because there is nothing to its right at that depth.

Interview points

The right side view holds one value per depth: the rightmost node of that depth.
A right-first DFS records a value the first time each depth is reached.
BFS keeps up to one level in the queue (O(w)); DFS keeps one path (O(h)).

Summary

Time O(n) for both versions.
The left child shows up in the view when no node to its right exists at the same depth.
Read queue.size() before the level loop, not inside its condition.