Right Side View of Binary Tree in DSA C - Build from Scratch

Right Side View of Binary Tree

📖 Scenario: Imagine you have a tree of boxes stacked in a special way. You want to see only the boxes that are visible when you look at the tree from the right side.

🎯 Goal: You will write a program in C to find the right side view of a binary tree. This means you will print the values of the nodes that are visible when looking from the right side.

📋 What You'll Learn

Create a binary tree with the exact nodes and structure given

Use a variable to keep track of the current level during traversal

Write a function to find and store the right side view nodes

Print the right side view nodes in order

💡 Why This Matters

🌍 Real World

Right side view of a binary tree helps in visualizing hierarchical data from a specific perspective, useful in UI layouts, organizational charts, and decision trees.

💼 Career

Understanding tree traversal and views is important for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree

Create the binary tree nodes with the exact structure: root node with value 1, root's left child with value 2, root's right child with value 3, node 2 has right child 5, node 3 has right child 4. Use the struct TreeNode and create pointers root, node2, node3, node5, and node4 accordingly.

DSA C

#include 
#include 

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int main() {

    // Create nodes and link them as described
    // Your code here

    return 0;
}

Hint

Use malloc to create each node and assign values and pointers exactly as described.

2

Add a Level Tracker Variable

Add an integer variable called max_level and set it to 0. This variable will help track the deepest level visited so far during traversal.

DSA C

#include 
#include 

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int main() {
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->right->val = 5;
    root->left->right->left = NULL;
    root->left->right->right = NULL;
    root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->right->val = 4;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // Add variable max_level here
    // Your code here

    return 0;
}

Hint

Declare int max_level = 0; inside main after creating the tree.

3

Write the Right Side View Function

Write a recursive function called rightSideViewUtil that takes parameters struct TreeNode *node, int level, int *max_level, and int *result. The function should visit the right child first, then the left child. When visiting a node at a level greater than *max_level, store the node's value in result at index level - 1 and update *max_level. Call this function from main with root, level 1, address of max_level, and an integer array result of size 10 initialized to zero.

DSA C

#include 
#include 

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void rightSideViewUtil(struct TreeNode *node, int level, int *max_level, int *result) {
    // Implement the recursive function here
    // Your code here
}

int main() {
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->right->val = 5;
    root->left->right->left = NULL;
    root->left->right->right = NULL;
    root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->right->val = 4;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    int max_level = 0;
    int result[10] = {0};

    rightSideViewUtil(root, 1, &max_level, result);

    // Your code here

    return 0;
}

Hint

Check if the node is NULL first. If the current level is greater than *max_level, save the node's value and update *max_level. Visit the right child before the left child recursively.

4

Print the Right Side View

Add a for loop in main to print the values stored in result from index 0 to max_level - 1. Print each value followed by a space.

DSA C

#include 
#include 

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void rightSideViewUtil(struct TreeNode *node, int level, int *max_level, int *result) {
    if (node == NULL) {
        return;
    }
    if (level > *max_level) {
        result[level - 1] = node->val;
        *max_level = level;
    }
    rightSideViewUtil(node->right, level + 1, max_level, result);
    rightSideViewUtil(node->left, level + 1, max_level, result);
}

int main() {
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->right->val = 5;
    root->left->right->left = NULL;
    root->left->right->right = NULL;
    root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->right->val = 4;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    int max_level = 0;
    int result[10] = {0};

    rightSideViewUtil(root, 1, &max_level, result);

    // Print the right side view values
    // Your code here

    return 0;
}

Hint

Use a for loop from 0 to max_level - 1 and print each value in result followed by a space.

Practice

1. What does the "Right Side View" of a binary tree represent?

easy

A. All leaf nodes of the tree

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from the right side

D. Nodes at the deepest level only

Solution

1. Step 1: Understand the view perspective

   The right side view shows nodes visible when looking at the tree from the right side.

2. Step 2: Identify visible nodes

   Only the rightmost node at each level is visible from the right side.

3. Final Answer:

   Nodes visible when the tree is viewed from the right side -> Option C

4. Quick Check:

   Right side view = rightmost nodes [OK]

Hint: Right side view shows rightmost nodes at each level [OK]

Common Mistakes:

• Confusing right side view with left side view
• Thinking it shows all leaf nodes
• Assuming it shows only deepest nodes

2. Which of the following C code snippets correctly declares a binary tree node structure for use in right side view algorithms?

easy

A. typedef struct Node { int val; struct Node* left; struct Node* right; } Node;

B. struct Node { int val; Node* left; Node* right; }; typedef Node;

C. typedef struct { int val; struct Node* left; struct Node* right; } Node;

D. struct Node { int val; struct Node left; struct Node right; }; typedef struct Node Node;

Solution

1. Step 1: Check struct declaration syntax

   typedef struct Node { int val; struct Node* left; struct Node* right; } Node; correctly declares a struct with pointers to left and right child nodes.

2. Step 2: Verify typedef usage

   typedef struct Node { int val; struct Node* left; struct Node* right; } Node; uses typedef properly to alias struct Node as Node.

3. Final Answer:

   typedef struct Node { int val; struct Node* left; struct Node* right; } Node; -> Option A

4. Quick Check:

   Correct struct with pointers and typedef [OK]

Hint: Use struct with pointers and typedef for node [OK]

Common Mistakes:

• Missing struct keyword before pointer types
• Using struct members as values instead of pointers
• Incorrect typedef syntax

3. Given the following binary tree and code snippet, what is the output of the right side view function?

    1
   / \
  2   3
   \   \
    5   4

// Function call: rightSideView(root);

medium

A. [1, 2, 4]

B. [1, 2, 5]

C. [1, 3, 5]

D. [1, 3, 4]

Solution

1. Step 1: Identify rightmost nodes at each level

   Level 0: Node 1; Level 1: Node 3; Level 2: Node 4.

2. Step 2: Collect nodes in order

   The right side view list is [1, 3, 4].

3. Final Answer:

   [1, 3, 4] -> Option D

4. Quick Check:

   Rightmost nodes per level = [1, 3, 4] [OK]

Hint: Pick rightmost node at each tree level [OK]

Common Mistakes:

• Choosing left child nodes instead of rightmost
• Including nodes not visible from right side
• Confusing node values at levels

4. The following C function attempts to print the right side view of a binary tree but has a bug. What is the error?

void rightSideViewHelper(Node* root, int level, int* maxLevel) {
    if (!root) return;
    if (level > *maxLevel) {
        printf("%d ", root->val);
        *maxLevel = level;
    }
    rightSideViewHelper(root->left, level + 1, maxLevel);
    rightSideViewHelper(root->right, level + 1, maxLevel);
}

medium

A. The function visits left child before right, so right side nodes may be missed

B. The maxLevel pointer is not updated correctly

C. The base case does not check for null root

D. The printf statement is missing a newline character

Solution

1. Step 1: Analyze traversal order

   The function visits left child before right child, so rightmost nodes may be overshadowed by left nodes.

2. Step 2: Understand impact on right side view

   Right side view requires visiting right child first to capture rightmost nodes at each level.

3. Final Answer:

   The function visits left child before right, so right side nodes may be missed -> Option A

4. Quick Check:

   Visit right child first for correct right side view [OK]

Hint: Traverse right child before left child [OK]

Common Mistakes:

• Visiting left child before right child
• Not updating maxLevel properly
• Ignoring base case for null nodes

5. You want to modify a function that returns the right side view of a binary tree to also return the left side view in a single traversal. Which approach is best?

hard

A. Perform two separate traversals: one right-first for right view, one left-first for left view

B. Use a single traversal visiting both children and track first node at each level for left and last for right

C. Use a single traversal visiting right child first, store rightmost nodes, then visit left child for leftmost nodes

D. Traverse only left child and assume it covers both views

Solution

1. Step 1: Understand views require different nodes

   Right view needs rightmost nodes; left view needs leftmost nodes at each level.

2. Step 2: Use single traversal with tracking

   Track first node seen at each level for left view and last node for right view during one traversal.

3. Step 3: Avoid separate traversals for efficiency

   This approach reduces time by combining both views in one pass.

4. Final Answer:

   Use a single traversal visiting both children and track first node at each level for left and last for right -> Option B

5. Quick Check:

   Track first and last nodes per level in one traversal [OK]

Hint: Track first and last nodes per level in one traversal [OK]

Common Mistakes:

• Doing two full traversals unnecessarily
• Visiting only one child and missing nodes
• Not tracking nodes per level properly