Why Left Side View of Binary Tree in DSA C?

The Big Idea

Discover how to see the hidden side of a tree without getting lost in its branches!

The Scenario

Imagine you have a tall tree in your backyard. You want to see which branches you can spot if you stand on the left side of the tree. But the tree is big and has many branches at different heights and depths.

Trying to list all visible branches from the left side by looking at each branch one by one is confusing and takes a lot of time.

The Problem

Manually checking each branch to see if it is visible from the left means you might miss some branches hidden behind others.

It is slow because you have to remember which branches you saw at each height and compare them all.

This manual method is error-prone and not practical for big trees.

The Solution

The Left Side View of a Binary Tree helps you see only the first branch you encounter at each level when looking from the left.

It uses a smart way to visit branches level by level and picks the first one at each height.

This way, you get a clear list of visible branches from the left side without confusion or missing any.

Before vs After

✗ Before

for each level in tree:
  for each node in level:
    if node is first in level:
      print(node.value)

✓ After

void leftSideView(Node* root) {
  if (root == NULL) return;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
      Node* current = q.front(); q.pop();
      if (i == 0) printf("%d ", current->value);
      if (current->left) q.push(current->left);
      if (current->right) q.push(current->right);
    }
  }
}

What It Enables

This concept lets you quickly find and list the visible nodes from the left side of any binary tree, no matter how big or complex.

Real Life Example

In a family tree, you might want to see the oldest ancestor visible from the left side at each generation level. The Left Side View helps you find those ancestors easily.

Key Takeaways

Manual checking of visible nodes is slow and error-prone.

Left Side View visits nodes level by level and picks the first node at each level.

This method gives a clear and quick list of visible nodes from the left side.

Practice

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

easy

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

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

C. All leaf nodes of the tree

D. Nodes at the deepest level of the tree

Solution

1. Step 1: Understand the view concept

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

2. Step 2: Differentiate from other views

   Right side view shows nodes from the right, leaf nodes are only the bottom nodes, and deepest level nodes are not necessarily visible from left.

3. Final Answer:

   Nodes visible when the tree is viewed from the left side -> Option A

4. Quick Check:

   Left side view = nodes visible from left [OK]

Hint: Left side view shows first node at each level from left [OK]

Common Mistakes:

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

2. Which of the following C code snippets correctly declares a binary tree node structure for computing the left side view?

easy

A. struct Node { int data; struct Node left; struct Node right; };

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

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

D. typedef struct { int data; struct Node* left; struct Node* right; } Node;

Solution

1. Step 1: Check correct struct declaration

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

2. Step 2: Identify errors in other options

   struct Node { int data; Node* left; Node* right; }; typedef Node; misses struct keyword before Node pointers, C uses struct Node instead of pointers causing infinite size, D misses struct name for pointers.

3. Final Answer:

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; -> Option B

4. Quick Check:

   Correct struct with pointers = typedef struct Node { int data; struct Node* left; struct Node* right; } Node; [OK]

Hint: Use pointers for left and right child nodes in struct [OK]

Common Mistakes:

• Using struct members instead of pointers causing infinite size
• Missing struct keyword before pointer types
• Incorrect typedef syntax

3. Given the following binary tree:

      1
     / \
    2   3
   /     \
  4       5

What is the left side view output printed by this C code?

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

void leftView(Node* root) {
  int maxLevel = 0;
  leftViewUtil(root, 1, &maxLevel);
}

medium

A. 1 3 5

B. 1 2 5

C. 1 2 4

D. 1 4 5

Solution

1. Step 1: Trace recursive calls and printing

   At level 1, print 1; level 2, print 2 (left child); level 3, print 4 (left child of 2). Right children at same levels are ignored since maxLevel is updated.

2. Step 2: Confirm output sequence

   Printed nodes are 1, 2, 4 in order with spaces.

3. Final Answer:

   1 2 4 -> Option C

4. Quick Check:

   Left side view nodes = 1 2 4 [OK]

Hint: Print first node at each level during preorder left-first traversal [OK]

Common Mistakes:

• Printing right child nodes before left
• Not updating maxLevel correctly
• Confusing left side view with right side view

4. Identify the bug in this C function intended to print the left side view of a binary tree:

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

medium

A. The condition should be 'level > *maxLevel' instead of 'level >= *maxLevel'

B. The function should print after recursive calls, not before

C. The base case should check 'if (root != NULL)' instead of 'if (root == NULL)'

D. The maxLevel pointer should be passed by value, not by reference

Solution

1. Step 1: Analyze the condition for printing

   The condition 'level >= *maxLevel' causes printing nodes multiple times at the same level, which is incorrect.

2. Step 2: Correct condition usage

   It should be 'level > *maxLevel' to print only the first node encountered at each level.

3. Final Answer:

   The condition should be 'level > *maxLevel' instead of 'level >= *maxLevel' -> Option A

4. Quick Check:

   Use strict greater than for first node per level [OK]

Hint: Use '>' not '>=' to print only first node at each level [OK]

Common Mistakes:

• Using '>=' causes duplicate prints at same level
• Printing after recursion changes order
• Incorrect base case logic

5. You want to print the left side view of a binary tree using a queue for level order traversal. Which approach correctly achieves this?

1. Enqueue root
2. While queue not empty:
   a. Get number of nodes at current level (size)
   b. For i in 0 to size-1:
       - Dequeue node
       - If i == 0, print node data
       - Enqueue left child if exists
       - Enqueue right child if exists

What is the output for this tree?

      10
     /  \
    20   30
      \    \
      40    50

hard

A. 10 40 50

B. 10 30 50

C. 10 20 50

D. 10 20 40

Solution

1. Step 1: Perform level order traversal with printing first node per level

   Level 1: print 10; Level 2: print 20 (first node at level); Level 3: print 40 (first node at level).

2. Step 2: Confirm output sequence

   Nodes printed in order: 10 20 40 with spaces.

3. Final Answer:

   10 20 40 -> Option D

4. Quick Check:

   Left side view by level order = 10 20 40 [OK]

Hint: Print first node at each level during BFS traversal [OK]

Common Mistakes:

• Printing last node instead of first at each level
• Mixing left and right child enqueue order
• Not counting nodes per level correctly