Right Side View of Binary Tree in DSA C

Mental Model

We want to see the nodes visible when looking at the tree from the right side, which means the rightmost node at each level.

Analogy: Imagine standing on the right side of a tall building with many floors. You only see the windows on the right edge of each floor, not the ones behind or to the left.

       1
      / \
     2   3
      \   \
       5   4

Right side view: 1 -> 3 -> 4

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3; 2 -> null, 5; 3 -> null, 4

Goal: Find the rightmost node at each level to form the right side view list

Step 1: Start level order traversal at root (level 0)

Level 0: [1]
Rightmost node: 1

Why: We begin from the top to capture nodes level by level

Step 2: Move to level 1, nodes are 2 and 3

Level 1: [2 -> 3]
Rightmost node: 3

Why: We want the rightmost node at this level, which is 3

Step 3: Move to level 2, nodes are 5 and 4

Level 2: [5 -> 4]
Rightmost node: 4

Why: At the last level, the rightmost visible node is 4

Result:

Right side view: 1 -> 3 -> 4

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define binary tree node
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Queue node for level order traversal
typedef struct QueueNode {
    TreeNode *node;
    struct QueueNode *next;
} QueueNode;

// Queue structure
typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

// Initialize queue
void initQueue(Queue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// Check if queue is empty
int isEmpty(Queue *q) {
    return q->front == NULL;
}

// Enqueue node
void enqueue(Queue *q, TreeNode *node) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// Dequeue node
TreeNode *dequeue(Queue *q) {
    if (isEmpty(q)) return NULL;
    QueueNode *temp = q->front;
    TreeNode *node = temp->node;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return node;
}

// Create new tree node
TreeNode *newTreeNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Print right side view of binary tree
void rightSideView(TreeNode *root) {
    if (root == NULL) return;
    Queue q;
    initQueue(&q);
    enqueue(&q, root);

    while (!isEmpty(&q)) {
        int levelSize = 0;
        QueueNode *temp = q.front;
        // Count nodes at current level
        while (temp != NULL) {
            levelSize++;
            temp = temp->next;
        }

        TreeNode *rightmost = NULL;
        for (int i = 0; i < levelSize; i++) {
            TreeNode *curr = dequeue(&q); // dequeue node at front
            rightmost = curr; // last node at this level will be rightmost
            if (curr->left != NULL) enqueue(&q, curr->left); // enqueue left child
            if (curr->right != NULL) enqueue(&q, curr->right); // enqueue right child
        }
        printf("%d", rightmost->val); // print rightmost node value
        if (!isEmpty(&q)) printf(" -> ");
    }
    printf("\n");
}

int main() {
    // Build tree from dry run example
    TreeNode *root = newTreeNode(1);
    root->left = newTreeNode(2);
    root->right = newTreeNode(3);
    root->left->right = newTreeNode(5);
    root->right->right = newTreeNode(4);

    rightSideView(root);
    return 0;
}

enqueue(&q, root);

Start level order traversal by adding root to queue

while (!isEmpty(&q)) {

Process nodes level by level until queue is empty

int levelSize = 0; QueueNode *temp = q.front; while (temp != NULL) { levelSize++; temp = temp->next; }

Count number of nodes at current level

TreeNode *rightmost = NULL; for (int i = 0; i < levelSize; i++) { TreeNode *curr = dequeue(&q); rightmost = curr;

Traverse all nodes at this level, keep track of last node as rightmost

if (curr->left != NULL) enqueue(&q, curr->left); if (curr->right != NULL) enqueue(&q, curr->right);

Add children of current node to queue for next level

printf("%d", rightmost->val); if (!isEmpty(&q)) printf(" -> ");

Print the rightmost node value of current level

Output

1 -> 3 -> 4

Complexity Analysis

Time: O(n) because we visit each node exactly once during level order traversal

Space: O(w) where w is the maximum width of the tree, due to queue storing nodes at each level

vs Alternative: Compared to DFS approach, BFS here naturally processes level by level making it easier to identify rightmost nodes; DFS requires tracking depth and overwriting values

Edge Cases

Empty tree (root is NULL)

No output is printed because there are no nodes

DSA C

if (root == NULL) return;

Tree with only one node

Prints the single node value as the right side view

DSA C

enqueue(&q, root);

Tree where all nodes only have left children

Right side view will be all nodes since each level has only one node

DSA C

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

When to Use This Pattern

When asked to find nodes visible from one side of a binary tree, use level order traversal and pick the last node at each level to get the side view.

Common Mistakes

Mistake: Printing the first node at each level instead of the last node
Fix: Track the last node processed at each level and print it after processing the entire level

Mistake: Not counting the number of nodes at each level, causing incorrect grouping
Fix: Count nodes at current level before processing to ensure correct level boundaries

Summary

Prints the rightmost node at each level of a binary tree to show the right side view.

Use when you want to see which nodes are visible when looking at the tree from the right side.

The key insight is to process the tree level by level and pick the last node at each level.

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