Left View of Binary Tree Editorial

Practice Problem Link: Left 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 left view of a binary tree contains the set of nodes that will be visible if you look at the binary tree from the left side.

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

Approach

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

Note: Visit the left subtree first followed by the right subtree.

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> leftView(Node* root) {
    queue<Node*> treeNodes;
	vector<int> treeLeftView;
	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) {
				treeLeftView.push_back(currentNode->data);
			}
			if (currentNode->left != NULL) {
				treeNodes.push(currentNode->left);
			}
			if (currentNode->right != NULL) {
				treeNodes.push(currentNode->right);
			}
		}
	}
	return treeLeftView;
}

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 getLeftView(Node* root, vector<int> &treeLeftView, int currentDepth, int &maxDepth) {
	if(root == NULL) {
		return;
	}
	currentDepth++;
	if(currentDepth > maxDepth) {
		treeLeftView.push_back(root->data);
		maxDepth = currentDepth;
	}
	getLeftView(root->left, treeLeftView, currentDepth, maxDepth);
	getLeftView(root->right, treeLeftView, currentDepth, maxDepth);
}
vector<int> leftView(Node* root) {
    vector<int> treeLeftView;
	int maxDepth = 0;
	getLeftView(root, treeLeftView, 0, maxDepth);
	return treeLeftView;
}

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[] leftView(Node root) {
	    Queue<Node> treeNodes = new LinkedList<Node> ();
		List<Integer> treeLeftView = 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) {
					treeLeftView.add(currentNode.data);
				}
				if (currentNode.left != null) {
					treeNodes.add(currentNode.left);
				}
				if (currentNode.right != null) {
					treeNodes.add(currentNode.right);
				}
			}
		}
		int[] temp = new int[treeLeftView.size()];
		for (int i = 0; i < treeLeftView.size(); i++) {
			temp[i] = treeLeftView.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 getLeftView(Node root, List<Integer> treeLeftView, int currentDepth) {
		if(root == null) {
			return;
		}
		currentDepth++;
		if(currentDepth > maxDepth) {
			treeLeftView.add(root.data);
			maxDepth = currentDepth;
		}
		getLeftView(root.left, treeLeftView, currentDepth);
		getLeftView(root.right, treeLeftView, currentDepth);
	}
	int[] leftView(Node root) {
		List<Integer> treeLeftView = new ArrayList<Integer> ();
		maxDepth = 0;
		getLeftView(root, treeLeftView, 0);
		int[] temp = new int[treeLeftView.size()];
		for(int i = 0; i < treeLeftView.size(); i++) {
			temp[i] = treeLeftView.get(i);
		}
		return temp;
	}
}