Right View of Binary Tree Editorial

Practice Problem Link: Right View of Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

There are different ways to look at a binary tree. The right view of a binary tree contains the set of nodes that will be visible if you look at the binary tree from the right side.

Given the root node of a binary tree, return an array containing the node elements in the right view, from top to bottom.

Approach

Traverse the given tree using level order traversal or preorder traversal and insert the last element of every level in the answer array while traversing.

Note: Visit the right subtree first followed by the left subtree to get the last element of every level.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++ (BFS)

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

vector<int> rightView(Node* root) {
    queue<Node*> treeNodes;
	vector<int> treeRightView;
	treeNodes.push(root);
	while (!treeNodes.empty()) {
		int n = treeNodes.size();
		for (int i = 0; i < n; i++) {
			Node* currentNode = treeNodes.front();
			treeNodes.pop();
			if (i == 0) {
				treeRightView.push_back(currentNode->data);
			}
			if (currentNode->right != NULL) {
				treeNodes.push(currentNode->right);
			}
			if (currentNode->left != NULL) {
				treeNodes.push(currentNode->left);
			}
		}
	}
	return treeRightView;
}

C++ (DFS)

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

void getRightView(Node* root, vector<int> &treeRightView, int currentDepth, int &maxDepth) {
	if(root == NULL) {
		return;
	}
	currentDepth++;
	if(currentDepth > maxDepth) {
		treeRightView.push_back(root->data);
		maxDepth = currentDepth;
	}
	getRightView(root->right, treeRightView, currentDepth, maxDepth);
	getRightView(root->left, treeRightView, currentDepth, maxDepth);
}
vector<int> rightView(Node* root) {
    vector<int> treeRightView;
	int maxDepth = 0;
	getRightView(root, treeRightView, 0, maxDepth);
	return treeRightView;
}

Java (BFS)

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	
	int[] rightView(Node root) {
	    Queue<Node> treeNodes = new LinkedList<Node> ();
		List<Integer> treeRightView = new ArrayList<Integer> ();
		treeNodes.add(root);
		while (!treeNodes.isEmpty()) {
			int n = treeNodes.size();
			for (int i = 0; i < n; i++) {
				Node currentNode = treeNodes.peek();
				treeNodes.poll();
				if (i == 0) {
					treeRightView.add(currentNode.data);
				}
				if (currentNode.right != null) {
					treeNodes.add(currentNode.right);
				}
				if (currentNode.left != null) {
					treeNodes.add(currentNode.left);
				}
			}
		}
		int[] temp = new int[treeRightView.size()];
		for (int i = 0; i < treeRightView.size(); i++) {
			temp[i] = treeRightView.get(i);
		}
		return temp;
	}
}

Java (DFS)

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	static int maxDepth;
	void getRightView(Node root, List<Integer> treeRightView, int currentDepth) {
		if(root == null) {
			return;
		}
		currentDepth++;
		if(currentDepth > maxDepth) {
			treeRightView.add(root.data);
			maxDepth = currentDepth;
		}
		getRightView(root.right, treeRightView, currentDepth);
		getRightView(root.left, treeRightView, currentDepth);
	}
	int[] rightView(Node root) {
		List<Integer> treeRightView = new ArrayList<Integer> ();
		maxDepth = 0;
		getRightView(root, treeRightView, 0);
		int[] temp = new int[treeRightView.size()];
		for(int i = 0; i < treeRightView.size(); i++) {
			temp[i] = treeRightView.get(i);
		}
		return temp;
	}
}