53. Binary Tree Right Side View

MediumBinary Trees & BSTsAlso on LeetCode ↗

Imagine standing to the right of the tree. Return the values of the nodes you can see, from top to bottom (the last node of each level).

Example 1

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Example 2

Input: root = [1,null,3]

Output: [1,3]

Hint 1

BFS: take the last node of every level.

Hint 2

DFS visiting right before left: the first node you meet at each depth is visible.

TreeBFSDFS

Reference solution for Right-first DFS (time O(n), space O(h)). Each solution passes every test in all four languages.

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(node, depth):          # visit right child first
            if not node:
                return
            if depth == len(res):      # first node seen at this depth
                res.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        dfs(root, 0)
        return res

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }
    private void dfs(TreeNode node, int depth, List<Integer> res) {
        if (node == null) return;
        if (depth == res.size()) res.add(node.val);   // first node at this depth
        dfs(node.right, depth + 1, res);
        dfs(node.left, depth + 1, res);
    }
}

class Solution {
    void dfs(TreeNode* node, int depth, vector<int>& res) {
        if (!node) return;
        if (depth == (int)res.size()) res.push_back(node->val);   // first node at this depth
        dfs(node->right, depth + 1, res);
        dfs(node->left, depth + 1, res);
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        dfs(root, 0, res);
        return res;
    }
};

function rightSideView(root) {
  const res = [];
  const dfs = (node, depth) => {
    if (!node) return;
    if (depth === res.length) res.push(node.val); // first node at this depth
    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  };
  dfs(root, 0);
  return res;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

53. Binary Tree Right Side View

Example 1

Example 2

Approach 1: BFS

Approach 2: Right-first DFS ✅