grid47 Exploring patterns and algorithms
Oct 18, 2024
6 min read
Solution to LeetCode 199: Binary Tree Right Side View Problem
You are given the root of a binary tree. Imagine yourself standing on the right side of the tree, and return the values of the nodes you can see when viewed from the right, ordered from top to bottom.
Problem
Approach
Steps
Complexity
Input: The input is a binary tree represented by the root node. The tree is defined as a TreeNode with properties: val, left, and right.
Example: root = [3,1,4,null,2]
Constraints:
• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100
Output: Return an array of integers representing the values of the nodes visible from the right side of the tree, ordered from top to bottom.
Example: [3,4,2]
Constraints:
• The output should be an array of integers.
Goal: The goal is to find the nodes that are visible from the right side of the binary tree.
Steps:
• Use level-order traversal (breadth-first search) of the tree.
• At each level, record the last node encountered in that level, as it is the one visible from the right.
• Return the recorded nodes in the order they are encountered from top to bottom.
Goal: The input tree will contain between 0 and 100 nodes, with each node's value between -100 and 100.
Steps:
• The tree can have a maximum of 100 nodes.
• Node values are between -100 and 100.
Assumptions:
• The binary tree is well-formed and follows the structure of a TreeNode.
• Input: root = [3,1,4,null,2]
• Explanation: In this example, when viewed from the right side, the visible nodes are 3 (root), 4 (right child of root), and 2 (right child of node 1). The output is [3, 4, 2].
• Input: root = [1, null, 2, null, 3]
• Explanation: Here, the right-side view is simply the nodes 1, 2, and 3, which are all in a straight line from top to bottom. The output is [1, 2, 3].
• Input: root = []
• Explanation: If the tree is empty, the right-side view is also empty, so the output is [].
Approach: The approach is to use level-order traversal (BFS) to process nodes level by level and keep track of the last node at each level. These are the nodes visible from the right side.
Observations:
• Each level of the tree is processed, and the last node in each level will be visible from the right side.
• Level-order traversal is efficient for this problem because it processes nodes level by level, allowing us to easily pick the last node from each level.
Steps:
• Initialize a queue to perform a breadth-first search (BFS) on the tree.
• For each level, traverse through all nodes, and record the last node at each level.
• Push all children of the current nodes onto the queue, then proceed to the next level.
• Return the list of last nodes from each level.
Empty Inputs:
• If the tree is empty, return an empty list.
Large Inputs:
• If the tree has a large number of nodes, the solution should still work efficiently, processing each node exactly once.
Special Values:
• Handle trees where all nodes are on one side, such as a left-leaning or right-leaning tree.
Constraints:
• Ensure that the time complexity remains linear with respect to the number of nodes.
Define the function 'rightSideView' which takes a pointer to the root node of a binary tree and returns a vector of integers representing the rightmost value at each level.
2 : Variable Initialization
vector<int> ans;
Initialize an empty vector 'ans' to store the rightmost values from each level of the binary tree.
3 : Base Case Check
if(!root) return ans;
Check if the tree is empty (root is null). If it is, return the empty vector 'ans'.
4 : Queue Initialization
list<TreeNode*> q;
Initialize a queue 'q' (implemented as a list) to help with the level-order traversal of the binary tree.
5 : Push Root to Queue
q.push_back(root);
Add the root node to the queue to start the traversal.
6 : While Loop - Level Traversal
while(!q.empty()) {
Start a while loop that runs as long as the queue is not empty, indicating there are still nodes to process.
7 : Result Vector Initialization
vector<int> res;
Initialize an empty vector 'res' to store the values of the current level of nodes.
8 : Queue Size
int sz = q.size();
Store the current size of the queue in 'sz', which represents the number of nodes at the current level.
9 : Inner While Loop - Process Nodes at Current Level
while(sz--) {
Process each node at the current level by iterating over the queue based on the number of nodes (sz).
10 : Queue Front Node
auto tmp = q.front();
Get the node at the front of the queue to process it.
11 : Pop Node from Queue
q.pop_front();
Remove the node from the front of the queue after processing it.
12 : Push Node Value to Result
res.push_back(tmp->val);
Add the value of the current node (tmp) to the 'res' vector.
13 : Left Child Check
if(tmp->left) q.push_back(tmp->left);
If the current node has a left child, add it to the queue for the next level of traversal.
14 : Right Child Check
if(tmp->right) q.push_back(tmp->right);
If the current node has a right child, add it to the queue for the next level of traversal.
15 : Push Rightmost Value to Answer
ans.push_back(res.back());
After processing all nodes at the current level, add the rightmost node value (the last value in 'res') to the 'ans' vector.
16 : Return Result
return ans;
Return the vector 'ans' containing the rightmost value at each level of the binary tree.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We visit each node once during the BFS traversal, making the time complexity O(n), where n is the number of nodes in the tree.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space used by the queue during the BFS traversal, where n is the number of nodes in the tree.
