Binary Tree Left Side View
Given a binary tree, return its left view: the nodes visible when you stand on the left side of the tree, ordered from top to bottom.
Intuition
1 12 / \3 2 34 / \ \5 4 5 6From the left you see 1, 2, 4. At each depth you see the leftmost node at that level. Node 2 hides node 3, and node 4 hides nodes 5 and 6.
This is the right side view with the two recursive calls swapped. Visit the left child first, and the first node reached at each new depth is the leftmost one there.
Approach: DFS, Left Child First
- Carry a
levelalong with the node (the root is level 0). - If
levelequals the current size of the answer, add this node's value. It is the first node reached at this depth. - Recurse on the left child first with
level + 1, then the right child.
For a BFS version, take the first node of every level instead of the last.
Code
class Solution {void dfs(Node* node, int level, vector<int>& ans) {if (node == nullptr) return;if (level == (int)ans.size()) ans.push_back(node->data);dfs(node->left, level + 1, ans);dfs(node->right, level + 1, ans);}public:vector<int> leftView(Node* root) {vector<int> ans;dfs(root, 0, ans);return ans;}};
Complexity
Time: O(n)
Every node is visited once.
Space: O(h)
Recursion stack depth equals the tree height.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"From the left you see one node per depth, the leftmost one. It is the right side view with the recursion order swapped. I do a DFS that visits the left child before the right child and carries the level. If the level equals the size of my answer list, I have not recorded this depth, so this is the first node at the depth, the leftmost, and I add it. Otherwise I skip it. A level order version would take the first node of each level. Time is O of n and space is O of h."
Next TopicSymmetric Tree