Binary Tree Right Side View
Understand and solve the interview question "Binary Tree Right Side View".
We'll cover the following...
Description
You are given a binary tree T
. Imagine you are standing to the right of it; you have to return the value of the nodes you can see from top to bottom.
You have to return the rightmost nodes on their respective levels in the form of an array.
Let’s discuss an example below:
Coding exercise
main.cpp
TreeNode.h
#include "TreeNode.h"std::vector<int> rightSideView(TreeNode* root){return {};}
Right-side view of binary tree
Solution
We can use a depth-first search (DFS) to solve this problem. The intuition here is to traverse the tree level by level recursively, starting from the rightmost
node for each recursive call.
Let’s review the implementation below:
main.cpp
TreeNode.h
#include "TreeNode.h"void DFS(TreeNode* node, int level, std::vector<int>& rightside) {if (level == rightside.size())rightside.push_back(node->val);if (node->right != nullptr)DFS(node->right, level + 1, rightside);if (node->left != nullptr)DFS(node->left, level + 1, rightside);}std::vector<int> rightSideView(TreeNode* root) {if (root == nullptr) return {};std::vector<int> rightside;DFS(root, 0, rightside);return rightside;}int main(){// Driver CodeTreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);root->right->right->left = new TreeNode(8);auto res = rightSideView(root);print(res);return 0;}
Right-side view of binary tree
Complexity measures
Time complexity | Space complexity |
---|---|