algoadvance

Leetcode 199. Binary Tree Right Side View

Problem Statement

Leetcode Problem 199 - Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

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

Clarifying Questions

1. What is the format of the tree nodes?
   • The tree nodes are in the form of a TreeNode class where each node has a val, left, and right.
2. Can the tree nodes contain negative values or zero?
   • Yes, tree node values can be any integer.
3. What should be returned if the tree is empty?
   • Return an empty list.

Strategy

We need to perform a level-order traversal (BFS) on the tree, but with a twist:

• For each level, we only need to keep track of the last node encountered.

Steps:

1. Use a queue to perform the BFS.
2. Track the last node of each level and add its value to the result list.

This method ensures that we are capturing the rightmost node at each level of the tree.

Code

#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

vector<int> rightSideView(TreeNode* root) {
    vector<int> result;
    if (!root) return result;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();
        int rightmostValue = 0;

        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            
            rightmostValue = node->val;  // capture the last element at this level
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        result.push_back(rightmostValue);  // add the last element of this level
    }

    return result;
}

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: O(n), where n is the number of nodes. In the worst case, the queue will contain all nodes of the tree (essentially when the tree is completely unbalanced). The result vector will also contain n values in the worst case (one for each level if the tree is highly unbalanced).

This solution efficiently captures the right side view of the binary tree by leveraging level-order traversal, ensuring clarity and correctness.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?