Binary Tree Right Side View
Problem Description
Question
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input:root=[1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input:root=[1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Example 3:
Input:root=[1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Solve it on LeetCode
Approaches
1. Level Order Traversal
Intuition:
The idea is to perform a level order traversal (BFS) of the tree. During the traversal, record the last node you encounter at each level, as that is the node visible from the right side for that level.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes in the tree since each node is visited once.
- Space Complexity: O(D), where D is the diameter of the tree, because the queue will hold at most one level of nodes.
2. DFS Preorder Traversal
Intuition:
We can use a modified DFS where we always attempt to visit the right child before the left child. This way, the first time we visit a new depth level, it's guaranteed to be the rightmost element. Store the value of such a node if the current depth is equal to the size of the result list.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes because we are potentially visiting all nodes.
- Space Complexity: O(H), where H is the height of the tree due to the recursion stack.