Bottom View of Binary Tree Editorial

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

Note: If there are multiple bottom-most nodes for a horizontal distance from root, use the later one in level-order traversal.

Given the root node of a binary tree, return an array containing the node elements in the bottom view, from 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, insert that node in the answer array. If there is already a node present corresponding to that distance in the answer array, update that index of the answer array with the new node.

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> bottomView(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;
		} else {
			if (distance < 0) {
				leftNodes[abs(distance) - 1] = currentNode->data;
			} else {
				rightNodes[distance] = currentNode->data;
			}
		}
		if (currentNode->left != NULL) {
			treeNodes.push({currentNode->left, distance - 1});
		}
		if (currentNode->right != NULL) {
			treeNodes.push({currentNode->right, distance + 1});
		}
	}
	vector<int> treeBottomView;
	for (int i = leftNodes.size() - 1; i >= 0; i--) {
		treeBottomView.push_back(leftNodes[i]);
	}
	for (int i = 0; i < rightNodes.size(); i++) {
		treeBottomView.push_back(rightNodes[i]);
	}
	return treeBottomView;
}

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[] bottomView(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);
			} else {
				if (distance < 0) {
					leftNodes.set(Math.abs(distance) - 1, currentNode.data);
				} else {
					rightNodes.set(distance, currentNode.data);
				}
			}
			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 greater than or equal to 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 getBottomView(Node* root, int distance, int depth, map<int, pair<int, int>> &treeBottomView) {
	if (root == NULL) {
		return;
	}
	if (treeBottomView.count(distance) == 0) {
		treeBottomView[distance] = {root->data, depth};
	}
	else if(depth >= treeBottomView[distance].second) {
		treeBottomView[distance] = {root->data, depth};
	}
	getBottomView (root->left, distance - 1, depth + 1, treeBottomView);
	getBottomView (root->right, distance + 1, depth + 1, treeBottomView);
	return;
}
vector<int> bottomView(Node* root) {
    map<int, pair<int, int>> treeBottomView;
	getBottomView (root, 0, 0, treeBottomView);
	vector<int> view;
	for(auto it: treeBottomView) {
		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 getBottomView(Node root, int distance, int depth, TreeMap <Integer,Pair> treeBottomView)
    { 
        if(root == null) {
        	return; 
		}
        if(!treeBottomView.containsKey(distance)) {
            treeBottomView.put(distance, new Pair(root.data, depth)); 
		}
		else if(treeBottomView.get(distance).second <= depth) {
            treeBottomView.put(distance, new Pair(root.data, depth));
		}
        getBottomView(root.left, distance - 1, depth + 1, treeBottomView);
        getBottomView(root.right, distance + 1, depth + 1, treeBottomView); 
    } 
	int[] bottomView(Node root) {
	    TreeMap<Integer,Pair> treeBottomView = new TreeMap<>();
		getBottomView (root, 0, 0, treeBottomView); 
		int[] view = new int[treeBottomView.size()];
		int indx = 0;
		for (Map.Entry<Integer, Pair> i: treeBottomView.entrySet()) {
            view[indx++] = i.getValue().first;
	    }
		return view;
	}
}