Programming : Right side view of a Binary Tree
Problem Statement: Given 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:
Code:
Approach-1: BFS
Explanation:
Initialize a queue data structure that would be useful for tree traversal and storing the nodes of the tree level by level. Initially add root to the queue. Then iterate over each level of the tree.
At each level, the last node of the level (i.e, the rightmost node) would be viewed from the right side.
Iterate over all the nodes on the current level. Remove the node from the front of the queue. The check (i == size-1) is important as we need to store only the last node of the level to the final output. Keep adding the children of a node in the queue and so on till we reach the last level.
At the end, return the list with the rightmost nodes in the tree.
Complexity Analysis:
Time Complexity: O(N), N is the number of nodes in the binary tree since we are visiting every node once.
Space Complexity: O(D) where D is the tree diameter.
Approach-2: DFS : Recursion
Explanation:
Traverse the tree level by level, starting each time from the rightmost child like the usual DFS recursive.
Complexity Analysis:
Time Complexity: O(N), N is the number of nodes in the binary tree since we are visiting every node once.
Space Complexity: O(H) to keep the recursion stack, where H is a tree height. In skewed tree, H = N in the worst case.
Github link to the solution:
Follow us on LinkedIn : DevelopersCoffee
Follow us on Twitter : DevelopersCoffee
Submit your story to : https://www.jotform.com/build/203200537740444 or drop a mail : coffee.devloper@gmail.com
