BFS-based views of a binary tree: top, left, and right nodes

Top View of Binary Tree | Level Order Traversal

Problem Statement Given the root of a binary tree, return the nodes visible when the tree is viewed from the top. For every horizontal distance (HD), only the first node encountered should be included. Brute Force Intuition In an interview, you can explain it like this: Compute the horizontal distance of every node and store all nodes belonging to the same horizontal distance. Finally, choose the topmost node for each horizontal distance. This requires storing multiple nodes for every horizontal distance. Complexity Time Complexity: O(N log N) Space Complexity: O(N) Moving Towards the Optimal Approach Notice that: BFS ↓ Processes Nodes Level by Level The first node encountered for a particular: Horizontal Distance will always be the topmost node. So we only need to store it once. Pattern Recognition Whenever you see: Top View Bottom View Vertical Traversal Think: Level Order Traversal + Horizontal Distance Key Observation Assign every node a: Horizontal Distance (HD) Rules: Root → 0 Left Child → HD - 1 Right Child → HD + 1 If an HD appears for the first time, store that node. Ignore all future nodes with the same HD. Optimal Approach Step 1 Perform BFS. Queue stores: (Node, HD) Step 2 Maintain: TreeMap<Integer, Integer> Key: Horizontal Distance Value: Node Value Step 3 If HD is not already present: map.put(hd, node.data); Step 4 Traverse the TreeMap from left to right. Optimal Java Solution class Pair { Node node; int hd; Pair(Node node, int hd) { this.node = node; this.hd = hd; } } class Solution { static ArrayList<Integer> topView(Node root) { ArrayList<Integer> ans = new ArrayList<>(); if (root == null) return ans; Queue<Pair> q = new LinkedList<>(); TreeMap<Integer, Integer> map = new TreeMap<>(); q.offer(new Pair(root, 0)); while (!q.isEmpty()) { Pair curr = q.poll(); if (!map.containsKey(curr.hd)) { map.put(curr.hd, curr.node.data); } if (curr.node.left != null) q.offer(new Pair( curr.node.left, curr.hd - 1)); if (curr.node.right != null) q.offer(new Pair( curr.node.right, curr.hd + 1)); } ans.addAll(map.values()); return ans; } } Dry Run 1 / \ 2 3 / \ / \ 4 5 6 7 Horizontal Distances: 4 → -2 2 → -1 1 → 0 3 → +1 7 → +2 Nodes: 5 6 are ignored because: HD already occupied Final Answer: [4,2,1,3,7] Why BFS Works? BFS visits nodes level by level. The first node encountered at each horizontal distance is always the highest (topmost) node. Once an HD is recorded, it should never be replaced. Complexity Analysis Metric Complexity Time Complexity O(N log N) Space Complexity O(N) log N comes from inserting keys into the TreeMap. Interview One-Liner Perform a level-order traversal while tracking horizontal distances, and store only the first node encountered for each horizontal distance. Pattern Learned BFS ↓ Horizontal Distance ↓ First Node ↓ Top View Similar Problems Top View of Binary Tree Bottom View of Binary Tree Vertical Order Traversal Vertical Sum Left View Right View Memory Trick Think: Horizontal Distance ↓ Seen Before? ↓ No ↓ Store It ↓ Ignore Future Nodes Mental Model Queue ↓ (Node, HD) ↓ First Node at HD ↓ Answer Whenever you hear: "Top View of Binary Tree" your brain should immediately think: BFS + Horizontal Distance + First Node

3 hours ago

Right View of a Binary Tree

leetcode.com Problem Statement Given the root of a binary tree, return the nodes visible when the tree is viewed from the right side. Only the last node at each level is visible. Brute Force Intuition In an interview, you can explain it like this: Perform a level-order traversal (BFS). For every level, record the last node encountered. Since BFS already processes nodes level by level, identifying the last node is straightforward. Complexity Time Complexity: O(N) Space Complexity: O(N) Moving Towards the Optimal Approach Notice that during BFS: Each Level ↓ Processed Together If we know: Level Size then the last node processed at that level is exactly the right view. Pattern Recognition Whenever you see: Left View Right View Level Wise Traversal Think: Level Order Traversal (BFS) Key Observation For every level: Last Node ↓ Right View Continue BFS until all levels are processed. Optimal Approach Step 1 Push the root into the queue. Step 2 Process one level at a time. size = queue.size(); Step 3 The last node: i == size - 1 belongs to the right view. Step 4 Push: Left Child ↓ Right Child into the queue. Optimal Java Solution class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) return ans; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { TreeNode curr = q.poll(); if (i == size - 1) ans.add(curr.val); if (curr.left != null) q.offer(curr.left); if (curr.right != null) q.offer(curr.right); } } return ans; } } Dry Run 1 / \ 2 3 / \ \ 4 5 6 Level 1 1 Last Node: 1 Level 2 2 3 Last Node: 3 Level 3 4 5 6 Last Node: 6 Final Answer: [1,3,6] Why BFS Works? BFS processes nodes level by level. Since nodes are visited from left to right, the last node processed at every level is exactly the node visible from the right side. Complexity Analysis Metric Complexity Time Complexity O(N) Space Complexity O(N) Interview One-Liner Perform a level-order traversal and record the last node encountered at every level. Pattern Learned Level Order ↓ Last Node ↓ Right View Similar Problems Right View of Binary Tree Left View of Binary Tree Top View Bottom View Zigzag Level Order Traversal Memory Trick Think: One Level ↓ Last Node ↓ Answer Mental Model Queue ↓ Process One Level ↓ Pick Last Node ↓ Continue Whenever you hear: "Right View of Binary Tree" your brain should immediately think: Level Order Traversal + Last Node of Every Level

3 hours ago

Left View of a Binary Tree

leetcode.com Problem Statement Given the root of a binary tree, return the nodes visible when the tree is viewed from the left side. Only the first node at each level is visible. Brute Force Intuition In an interview, you can explain it like this: Perform a level-order traversal (BFS). For every level, simply record the first node encountered. Since BFS already processes nodes level by level, identifying the first node is straightforward. Complexity Time Complexity: O(N) Space Complexity: O(N) Moving Towards the Optimal Approach Notice that during BFS: Each Level ↓ Processed Together If we know: Level Size then the very first node processed at that level is exactly the left view. Pattern Recognition Whenever you see: Left View Right View Level Wise Processing Think: Level Order Traversal (BFS) Key Observation For every level: First Node ↓ Left View Continue BFS until all levels are processed. Optimal Approach Step 1 Push the root into a queue. Step 2 Process one level at a time. For every level: size = queue.size(); Step 3 The first node: i == 0 belongs to the left view. Step 4 Push: Left Child ↓ Right Child into the queue. Optimal Java Solution class Solution { ArrayList<Integer> leftView(Node root) { ArrayList<Integer> ans = new ArrayList<>(); if (root == null) return ans; Queue<Node> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { Node curr = q.poll(); if (i == 0) ans.add(curr.data); if (curr.left != null) q.offer(curr.left); if (curr.right != null) q.offer(curr.right); } } return ans; } } Dry Run 1 / \ 2 3 / \ \ 4 5 6 Level 1 1 First Node: 1 Level 2 2 3 First Node: 2 Level 3 4 5 6 First Node: 4 Final Answer: [1,2,4] Why BFS Works? BFS processes the tree level by level. Since nodes are visited from left to right, the first node encountered at every level is exactly the node visible from the left side. Complexity Analysis Metric Complexity Time Complexity O(N) Space Complexity O(N) Interview One-Liner Perform a level-order traversal and record the first node encountered at every level. Pattern Learned Level Order ↓ First Node ↓ Left View Similar Problems Left View of Binary Tree Right View of Binary Tree Top View Bottom View Zigzag Level Order Traversal Memory Trick Think: One Level ↓ First Node ↓ Answer Mental Model Queue ↓ Process One Level ↓ Pick First Node ↓ Continue Whenever you hear: "Left View of Binary Tree" your brain should immediately think: Level Order Traversal + First Node of Every Level

3 hours ago