Right View of Binary Tree in C++

Problem Description

You are given a binary tree.
You need to find the nodes in order of top to bottom which will be visible when the tree is viewed from the right side.

Right view :-


The visible nodes from top to bottom are 1, 3 and 4.

Input format
First line contains an integer n - Number of nodes.
Second line contains n space separated integers - The value of nodes.
Next n lines contain 3 space separated integers i, l, r describing left and right child of ith node as l and r respectively.

Output format
Output space separated values of the nodes visible from right side of the tree from top to bottom.

Sample Input 1
6
10 15 25 12 40 16
4 -1 -1
1 5 3
5 6 -1
6 -1 -1
2 -1 -1
3 2 4

Sample Output 1
10 25 12

Solution
To solve the problem of finding the nodes visible from the right side of a binary tree, we need to perform a level-order traversal (breadth-first traversal) and keep track of the last node seen at each level. This approach ensures that we capture the rightmost nodes at each level, which are the ones visible from the right side.

### Steps to Solve the Problem
1. **Construct the Binary Tree**: Read the input values to construct the binary tree.
2. **Perform Level-Order Traversal**: Use a queue to perform a level-order traversal. For each level, keep track of the last node encountered.
3. **Store and Output the Rightmost Nodes**: Store the values of the rightmost nodes at each level and print them.

### Implementation in C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BinaryTree {
public:
TreeNode* createTree(const vector<int>& values, const vector<pair<int, int>>& children, int index) {
if (index == -1) return nullptr;
TreeNode* node = new TreeNode(values[index - 1]);
node->left = createTree(values, children, children[index - 1].first);
node->right = createTree(values, children, children[index - 1].second);
return node;
}

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();
TreeNode* lastNode = nullptr;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = q.front();
q.pop();
lastNode = node;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}

if (lastNode) result.push_back(lastNode->val);
}
return result;
}
};

int main() {
int n;
cin >> n;
vector<int> values(n);
for (int i = 0; i < n; ++i) {
cin >> values[i];
}

vector<pair<int, int>> children(n);
for (int i = 0; i < n; ++i) {
int node, left, right;
cin >> node >> left >> right;
children[node - 1] = {left, right};
}

BinaryTree bt;
TreeNode* root = bt.createTree(values, children, 1);
vector<int> rightView = bt.rightSideView(root);

for (int val : rightView) {
cout << val << " ";
}
cout << endl;
return 0;
}

### Explanation
1. **TreeNode Class**: Represents each node in the binary tree with a value and pointers to left and right children.
2. **BinaryTree Class**:
- **createTree Function**: Constructs the binary tree from the input values and child indices.
- **rightSideView Function**: Performs a level-order traversal to find the rightmost nodes visible from the right side.
3. **main Function**:
- Reads the input values.
- Constructs the binary tree using the `createTree` function.
- Computes the right side view using the `rightSideView` function.
- Prints the result.

### Input and Output

- **Input**: The first line contains the number of nodes `n`. The second line contains `n` space-separated integers representing the values of the nodes. The next `n` lines contain three integers each, representing the node index and its left and right children.

- **Output**: A space-separated list of values of the nodes visible from the right side of the tree from top to bottom.

### Sample Input and Output

- **Sample Input**:
```
6
10 15 25 12 40 16
4 -1 -1
1 5 3
5 6 -1
6 -1 -1
2 -1 -1
3 2 4
```

- **Sample Output**:

```
10 25 12
```

This implementation ensures that we capture the nodes visible from the right side of the binary tree using a straightforward level-order traversal approach.

For Left View, the implementation is here:

To modify the code to get the left view of the binary tree instead of the right view, you need to adjust the traversal logic to keep track of the first node encountered at each level during a level-order traversal (breadth-first traversal). This will ensure that we capture the leftmost nodes at each level, which are the ones visible from the left side.

Here is the updated implementation for the left view of the binary tree:

### C++ Implementation

```cpp

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

class TreeNode {

public:

    int val;

    TreeNode* left;

    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

class BinaryTree {

public:

    TreeNode* createTree(const vector<int>& values, const vector<pair<int, int>>& children, int index) {

        if (index == -1) return nullptr;

        TreeNode* node = new TreeNode(values[index - 1]);

        node->left = createTree(values, children, children[index - 1].first);

        node->right = createTree(values, children, children[index - 1].second);

        return node;

    }

    vector<int> leftSideView(TreeNode* root) {

        vector<int> result;

        if (!root) return result;

        

        queue<TreeNode*> q;

        q.push(root);

        

        while (!q.empty()) {

            int levelSize = q.size();

            TreeNode* firstNode = nullptr;

            

            for (int i = 0; i < levelSize; ++i) {

                TreeNode* node = q.front();

                q.pop();

                if (i == 0) { // Capture the first node at this level

                    firstNode = node;

                }

                

                if (node->left) q.push(node->left);

                if (node->right) q.push(node->right);

            }

            

            if (firstNode) result.push_back(firstNode->val);

        }

        

        return result;

    }

};

int main() {

    int n;

    cin >> n;

    vector<int> values(n);

    for (int i = 0; i < n; ++i) {

        cin >> values[i];

    }

    vector<pair<int, int>> children(n);

    for (int i = 0; i < n; ++i) {

        int node, left, right;

        cin >> node >> left >> right;

        children[node - 1] = {left, right};

    }

    BinaryTree bt;

    TreeNode* root = bt.createTree(values, children, 1);

    vector<int> leftView = bt.leftSideView(root);

    for (int val : leftView) {

        cout << val << " ";

    }

    cout << endl;

    return 0;

}

```

### Explanation

1. **TreeNode Class**: Represents each node in the binary tree with a value and pointers to left and right children.

2. **BinaryTree Class**:

   - **createTree Function**: Constructs the binary tree from the input values and child indices.

   - **leftSideView Function**: Performs a level-order traversal to find the leftmost nodes visible from the left side.

3. **main Function**:

   - Reads the input values.

   - Constructs the binary tree using the `createTree` function.

   - Computes the left side view using the `leftSideView` function.

   - Prints the result.

### Input and Output

- **Input**: The first line contains the number of nodes `n`. The second line contains `n` space-separated integers representing the values of the nodes. The next `n` lines contain three integers each, representing the node index and its left and right children.

- **Output**: A space-separated list of values of the nodes visible from the left side of the tree from top to bottom.

### Sample Input and Output

- **Sample Input**:

    ```

    6

    10 15 25 12 40 16

    4 -1 -1

    1 5 3

    5 6 -1

    6 -1 -1

    2 -1 -1

    3 2 4

    ```

- **Sample Output**:

    ```

    10 15 16

    ```

This modified implementation ensures that we capture the nodes visible from the left side of the binary tree using a straightforward level-order traversal approach. The key change is to capture the first node encountered at each level during the traversal.