Left Side View of Binary Tree in DSA C++

Mental Model

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

Analogy: Imagine standing on the left side of a tall building with many floors and windows; you only see the first window on each floor from your side.

      1
     / \
    2   3
   / \   \
  4   5   6

Left side view: 1 -> 2 -> 4 -> null

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Print the left side view nodes: the first node visible at each level from left side

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

Level 0: [1]
Left side node: 1

Why: Root is always visible from left side

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

Level 1: [2, 3]
Left side node: 2

Why: At level 1, first node from left is 2

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

Level 2: [4, 5, 6]
Left side node: 4

Why: At level 2, first node from left is 4

Result:

Left side view: 1 -> 2 -> 4 -> null

Annotated Code

DSA C++

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

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

vector<int> leftSideView(TreeNode* root) {
    vector<int> result;
    if (!root) return result; // handle empty tree

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

    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (i == 0) {
                result.push_back(node->val); // first node at this level
            }

            if (node->left) q.push(node->left); // enqueue left child
            if (node->right) q.push(node->right); // enqueue right child
        }
    }
    return result;
}

int main() {
    // Construct the tree from dry_run input
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    vector<int> view = leftSideView(root);
    for (int val : view) {
        cout << val << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

if (!root) return result; // handle empty tree

return empty if tree is empty

q.push(root);

start BFS from root

int levelSize = q.size();

get number of nodes at current level

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

iterate over all nodes at this level

TreeNode* node = q.front(); q.pop();

process current node and remove from queue

if (i == 0) { result.push_back(node->val); }

record first node at this level for left view

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

enqueue left child for next level

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

enqueue right child for next level

Output

1 -> 2 -> 4 -> null

Complexity Analysis

Time: O(n) because we visit each node exactly once in the breadth-first traversal

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

vs Alternative: Compared to a depth-first approach with extra bookkeeping, BFS naturally processes nodes level by level, making it simpler and efficient for this problem

Edge Cases

Empty tree

Returns empty list since there are no nodes

DSA C++

if (!root) return result; // handle empty tree

Tree with only root node

Returns list with only root value

DSA C++

if (i == 0) { result.push_back(node->val); }

Tree with nodes only on right side

Still returns first node at each level, which will be the right nodes

DSA C++

if (i == 0) { result.push_back(node->val); }

When to Use This Pattern

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

Common Mistakes

Mistake: Collecting all nodes at each level instead of only the first node
Fix: Only add the node value to result when processing the first node at each level (i == 0)

Mistake: Using depth-first traversal without tracking levels properly
Fix: Use breadth-first traversal (queue) to process nodes level by level

Summary

Prints the first node visible at each level when looking at the tree from the left side.

Use when you need to see the leftmost nodes of each level in a binary tree.

The key insight is to do a level order traversal and record only the first node at each level.