JavaScript Algorithms: Binary Tree Right Side View (LeetCode)
Description
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:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation: 1 <---
/ \
2 3 <---
\ \
5 4 <---
Solution
Every time when you face a problem where you need to go through a tree level by level you should think about BFS — Breadth-first search.
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a search key) and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level — wiki.
We can implement BFS using queue (Array in JavaScript). The first item in the queue will be the root node. After that, we’re going through the queue until it’s not empty and pushing the last item from each level.
It’s almost done, but we can optimize it a little. In this case, we need to get only the last item in each row (right), so we don’t need to store all level values.
I hope, it was useful for you. Thanks for reading! Looking forward to your feedback. See you soon ✌️
