DSA 450 Notes

Problem Statement

Given a binary tree, print the left view of the tree. The left view contains all nodes that are the first nodes in their level when viewed from the left side.

Example:

Input: Root of the above tree
Output: [1, 2, 4]

Approach 1: Brute Force (Level Order with First Element)

Intuition

Perform level order traversal and for each level, take only the first element.

Algorithm

Use BFS to traverse level by level
For each level, add only the first node to result
Continue until all levels are processed

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> leftViewBFS(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                
                // First node of each level
                if (i == 0) {
                    result.add(node.val);
                }
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n) - Each node is visited once
Space Complexity: O(n) - Queue can hold up to n/2 nodes

Approach 2: Optimal (DFS with Level Tracking)

Intuition

Use DFS and track the maximum level seen so far. When visiting a node at a new level for the first time (going left first), add it to the result.

Algorithm

Traverse left subtree before right subtree
Track the current level and max level seen
If current level > max level, add node to result
Update max level

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int maxLevel = 0;
    
    public List<Integer> leftView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        maxLevel = 0;
        leftViewDFS(root, 1, result);
        return result;
    }
    
    private void leftViewDFS(TreeNode root, int level, List<Integer> result) {
        if (root == null) return;
        
        // First node of this level
        if (level > maxLevel) {
            result.add(root.val);
            maxLevel = level;
        }
        
        // Left before right to get left view
        leftViewDFS(root.left, level + 1, result);
        leftViewDFS(root.right, level + 1, result);
    }
    
    // Alternative: Using result size as level tracker
    public List<Integer> leftViewAlt(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        leftViewDFSAlt(root, 1, result);
        return result;
    }
    
    private void leftViewDFSAlt(TreeNode root, int level, List<Integer> result) {
        if (root == null) return;
        
        if (result.size() < level) {
            result.add(root.val);
        }
        
        leftViewDFSAlt(root.left, level + 1, result);
        leftViewDFSAlt(root.right, level + 1, result);
    }
}

Complexity Analysis

Time Complexity: O(n) - Each node is visited exactly once
Space Complexity: O(h) - Recursion stack depth equals tree height

Key Takeaways

Left view = first node at each level when traversing left to right
BFS approach: Take first element of each level
DFS approach: Visit left child before right, track max level seen
Using result.size() < level is a clever way to avoid global variable
Left view and right view are symmetric problems - just swap left/right priority

Left View of a tree

Problem Statement

Approach 1: Brute Force (Level Order with First Element)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (DFS with Level Tracking)

Intuition

Algorithm

Complexity Analysis

Key Takeaways