Bottom view of BT
MetaThe problem
Given root of binary tree, return the** bottom view** of the binary tree.
The bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom. Return nodes from the leftmost node to the rightmost node. Also if 2 nodes are outside the shadow of the tree and are at the same position then consider the node that appears later in level traversal.
Input : root = [20, 8, 22, 5, 3, null, 25, null, null, 10 ,14] Output : [5, 10, 3, 14, 25] Explanation : From left to right the path is as follows : First we encounter node with value 5. Then we have nodes 8 , 10 but from bottom only 10 will be visible. Next we have 20 , 3 but from bottom only 3 will be visible. Next we have 14 , 22 but from bottom only 14 will be visible. Then we encounter node with value 25.
Input : root = [20, 8, 22, 5, 3, 4, 25, null, null, 10 ,14] Output : [5, 10, 4, 14, 25] **Explanation : **From left to right the path is as follows : First we encounter node with value 5. Then we have nodes 8 , 10 but from bottom only 10 will be visible. Next we have 20 , 3 and 4. The 3 and 4 will be nodes visible from bottom but as the node 4 appears later from left to right , so only node 4 will be considered visible. Next we have 14 , 22 but from bottom only 14 will be visible. Then we encounter node with value 25.
Input: root = [10, 20, 30, 40, 60]
- 1 <= Number of Nodes <= 104
- -103 <= Node.val <= 103
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
vector <int> bottomView(TreeNode *root){
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public List<Integer> bottomView(TreeNode root) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.data = val
# self.left = left
# self.right = right
class Solution:
def bottomView(self, root):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
bottomView(root) {
//your code goes here
}
}csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
*/
public class Solution
{
public List<int> bottomView(TreeNode root)
{
//your code goes here
}
}go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Data int
* Left *TreeNode
* Right *TreeNode
* }
*/
func bottomView(root *TreeNode) []int {
}Stuck? Show a way to structure it+
- 01Traverse with horizontal distance and depth.
- 02Record the candidate for each horizontal distance.
- 03Replace when a node is deeper, respecting required tie order.
- 04Emit values from smallest to largest horizontal distance.
Reference answer
Then expect these follow-ups
How does top view change the overwrite rule?
Tests: view comparison
How would you handle equal-depth ties deterministically?
Tests: traversal order
Hiring now
Get the Meta interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question