Bottom View of Binary Tree

 https://workat.tech/problem-solving/practice/bottom-view-binary-tree

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.

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has 2 lines:

• The first line contains an integer n denoting the number of nodes in the tree (including the NULL nodes).
• The second line contains n space-separated integers that will form the binary tree. The integers follow level order traversal of the tree where -1 indicates a NULL node.

Output Format

For each test case, the output contains a line with space-separated integers representing the bottom view of the binary tree.

Sample Input

5
7
1 2 -1 4 -1 5 6
3
6 -1 4
7
8 -1 9 -1 10 11 12
5
28 14 11 -1 48
1
6

Expected Output

5 4 6 1
6 4
8 11 10 12
14 48 11
6

1 <= T <= 10
1 <= n <= 105
1 <= node value <= 106

---

Intuition

Level Order  Q based BFS

Pair (Node, col)

Map<Integer, Integer> - col to node.val

At each col, the last node.val is visible from bottom

--

Time Complexity - O(N)

Space Complexity - O(N)

--

Related problems

top-view-of-binary-tree

199-binary-tree-right-side-view

	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 node;
	int col;
	Pair(Node n, int c) {
	node = n;
	col = c;
	}
	}
	int[] bottomView(Node root) {
	if (root == null) {
	return new int[0];
	}
	List<Integer> list = new ArrayList<Integer>();
	Queue<Pair> q = new LinkedList<Pair>();
	q.offer(new Pair(root, 0));
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
	while (!q.isEmpty()) {
	int size = q.size();
	for (int i = 0; i < q.size(); i++) {
	Pair pair = q.poll();
	min = Math.min(min, pair.col);
	max = Math.max(max, pair.col);
	map.put(pair.col, pair.node.data);
	if (pair.node.left != null) {
	q.offer(new Pair(pair.node.left, pair.col - 1));
	}
	if (pair.node.right != null) {
	q.offer(new Pair(pair.node.right, pair.col + 1));
	}
	}
	}
	int[] ans = new int[map.size()];
	for (int i = min, j = 0; i <= max; i++, j++) {
	ans[j] = map.get(i);
	}
	return ans;
	}
	}

view raw BottomViewOfBinaryTreeBFS.java hosted with ❤ by GitHub