Top View of Binary Tree Editorial

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

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

Note: The first level is traversed left to right.

Approach (BFS)

The idea is based on the level order traversal of the given tree using a queue.

• While traversing the given tree in the level order way, we will keep the track of horizontal distance of each node from the root node.
• For every node found at a certain distance for the first time, insert that node in the answer array.

Note: Use two different arrays to store the left side nodes and right side nodes w.r.t the root node and finally merge both the arrays.

Analysis

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

Implementation

C++

/* 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> topView(Node* root) {
    queue<pair<Node*, int>> treeNodes;
	unordered_map<int,int> visitedDistance;
	vector<int> leftNodes, rightNodes;
	treeNodes.push({root, 0});
	while (!treeNodes.empty()) {
		Node* currentNode = treeNodes.front().first;
		int distance = treeNodes.front().second;
		treeNodes.pop();
		if (visitedDistance[distance] == 0) {
			if (distance < 0) {
				leftNodes.push_back(currentNode->data);
			} else {
				rightNodes.push_back(currentNode->data);
			}
			visitedDistance[distance] = 1;
		}
		if (currentNode->left != NULL) {
			treeNodes.push({currentNode->left, distance - 1});
		}
		if (currentNode->right != NULL) {
			treeNodes.push({currentNode->right, distance + 1});
		}
	}
	vector<int> treeTopView;
	for (int i = leftNodes.size() - 1; i >= 0; i--) {
		treeTopView.push_back(leftNodes[i]);
	}
	for (int i = 0; i < rightNodes.size(); i++) {
		treeTopView.push_back(rightNodes[i]);
	}
	return treeTopView;
}

Java

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;
		}
	}
	*/
	class Pair {
		Node first;
		int second;
		Pair (Node x, int y) {
			first = x;
			second = y;
		}
	}
	int[] topView(Node root) {
	    Queue<Pair> treeNodes = new LinkedList<>();
		HashMap<Integer, Integer> visitedDistance = new HashMap<>();
		List<Integer> leftNodes = new ArrayList<> ();
		List<Integer> rightNodes = new ArrayList<> ();
		treeNodes.add(new Pair(root, 0));
		while (!treeNodes.isEmpty()) {
			Node currentNode = treeNodes.peek().first;
			int distance = treeNodes.peek().second;
			treeNodes.poll();
			if (visitedDistance.get(distance) == null) {
				if (distance < 0) {
					leftNodes.add(currentNode.data);
				} else {
					rightNodes.add(currentNode.data);
				}
				visitedDistance.put(distance, 1);
			}
			if (currentNode.left != null) {
				treeNodes.add(new Pair(currentNode.left, distance - 1));
			}
			if (currentNode.right != null) {
				treeNodes.add(new Pair(currentNode.right, distance + 1));
			}
		}
		int[] treeTopView = new int[leftNodes.size() + rightNodes.size()];
		int indx = 0;
		for (int i = leftNodes.size() - 1; i >= 0; i--) {
			treeTopView[indx++] = leftNodes.get(i);
		}
		for (int i = 0; i < rightNodes.size(); i++) {
			treeTopView[indx++] = rightNodes.get(i);
		}
		return treeTopView;
	}
}

Approach (DFS)

The idea is to use a map to store the top view of the tree during the traversal. 

• We will keep track of the depth and horizontal distance from the root for every node in the tree. The horizontal distance will work as the key in the map.
• For every node found at a certain distance, we will update the node value stored in the map if the depth of the new node is less than the one stored in the map.

Analysis

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

Implementation

C++

/* 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 getTopView(Node* root, int distance, int depth, map<int, pair<int, int>> &treeTopView) {
	if (root == NULL) {
		return;
	}
	if (treeTopView.count(distance) == 0) {
		treeTopView[distance] = {root->data, depth};
	}
	else if(depth < treeTopView[distance].second) {
		treeTopView[distance] = {root->data, depth};
	}
	getTopView (root->left, distance - 1, depth + 1, treeTopView);
	getTopView (root->right, distance + 1, depth + 1, treeTopView);
	return;
}
vector<int> topView(Node* root) {
    map<int, pair<int, int>> treeTopView;
	getTopView (root, 0, 0, treeTopView);
	vector<int> view;
	for(auto it: treeTopView) {
		view.push_back(it.second.first);
	}
	return view;
}

Java

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;
		}
	}
	*/
	class Pair {
        int first;
        int second;
        
        Pair(int x, int y)
        {
            first = x;
            second = y;
        }
    }
	void getTopView(Node root, int distance, int depth, TreeMap <Integer,Pair> treeTopView)
    { 
        if(root == null) {
        	return; 
		}
        if(!treeTopView.containsKey(distance)) {
            treeTopView.put(distance, new Pair(root.data, depth)); 
		}
		else if(treeTopView.get(distance).second > depth) {
            treeTopView.put(distance, new Pair(root.data, depth));
		}
        getTopView(root.left, distance - 1, depth + 1, treeTopView);
        getTopView(root.right, distance + 1, depth + 1, treeTopView); 
    } 
	int[] topView(Node root) {
		TreeMap<Integer,Pair> treeTopView = new TreeMap<>();
		getTopView (root, 0, 0, treeTopView); 
		int[] view = new int[treeTopView.size()];
		int indx = 0;
		for (Map.Entry<Integer, Pair> i: treeTopView.entrySet()) {
            view[indx++] = i.getValue().first;
	    }
		return view; 
	}
}