Bottom View of Binary Tree

Medium
1964.

Bottom View of Binary Tree

Bottom View of Binary Tree is a medium coding problem on hash table, breadth-first search and trees, asked in Amazon, Flipkart and Walmart interviews.

Given the root of a binary tree, return its bottom view: the values you would see looking up at the tree from below, listed from the leftmost column to the rightmost.

The root is in column 0; a node's left child is one column to the left and its right child one column to the right. For each column, the visible node is the deepest one; if several nodes of a column share the greatest depth, the one that comes last in a left-to-right level-order traversal is visible.

Example 1

Input
root = [20,8,22,5,3,null,25,null,null,10,14]
Output
[5,10,3,14,25]
Explanation
Column 0 holds 20 and, lower down, 3. Column −1 holds 8 and 10, column 1 holds 22 and 14 — in each the lower node shows.

Example 2

Input
root = [1,2,3,4,5,6,7]
Output
[4,2,6,3,7]
Explanation
5 and 6 share column 0 at the same depth; 6 comes later in level order, so it is the one seen.

Example 3

Input
root = [7]
Output
[7]
Explanation
A single node is its own bottom view.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var bottomView = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Bottom View of Binary Tree — Solution in Python, Java & C++

Bottom View of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Bottom View of Binary Tree is a medium coding problem on hash table, breadth-first search and trees, asked in Amazon, Flipkart and Walmart interviews.

Problem statement

Given the root of a binary tree, return its bottom view: the values you would see looking up at the tree from below, listed from the leftmost column to the rightmost.

The root is in column 0; a node's left child is one column to the left and its right child one column to the right. For each column, the visible node is the deepest one; if several nodes of a column share the greatest depth, the one that comes last in a left-to-right level-order traversal is visible.

Example 1

Input: root = [20,8,22,5,3,null,25,null,null,10,14]
Output: [5,10,3,14,25]
Explanation: Column 0 holds 20 and, lower down, 3. Column −1 holds 8 and 10, column 1 holds 22 and 14 — in each the lower node shows.

Example 2

Input: root = [1,2,3,4,5,6,7]
Output: [4,2,6,3,7]
Explanation: 5 and 6 share column 0 at the same depth; 6 comes later in level order, so it is the one seen.

Example 3

Input: root = [7]
Output: [7]
Explanation: A single node is its own bottom view.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5

Hints for Bottom View of Binary Tree

  1. Hint 1

    Number the columns: root 0, left child column − 1, right child column + 1.

  2. Hint 2

    In a level-order traversal, a later node is never shallower than an earlier one, and ties at the same depth go left to right.

  3. Hint 3

    So run a BFS carrying columns and simply overwrite each column's entry with every node you meet — the last write is the visible node.

How to solve Bottom View of Binary Tree

A breadth-first traversal meets nodes in non-decreasing depth, left to right within a depth. The last node recorded for a column is therefore its deepest, and among the deepest the last in level order — exactly the bottom-view rule.

Approach

  1. Run a BFS from the root carrying each node's column (left c - 1, right c + 1).
  2. For every node, set view[column] = node.val, overwriting what was there.
  3. Track the smallest and largest column.
  4. Return view[min], …, view[max].

Why it works

When BFS reaches a node, every node before it in the queue is at most as deep, and nodes of the same depth before it lie to its left in level order. Overwriting keeps the latest visit, which is the deepest node of the column and, among equals, the last in level order.

Complexity

  • Time — O(n) with an array indexed by column (O(n log n) with a sorted map)
  • Space — O(n)

Pitfalls

  • A depth-first traversal can reach a shallower node of a column after a deeper one; it needs explicit depth comparisons.
  • For a tie at the same depth the later node in level order wins — the opposite of the top view's rule.

Reference solution

Python

from typing import List, Optional

def bottomView(root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    view = {}
    queue = [(root, 0)]
    head = 0
    while head < len(queue):
        node, col = queue[head]
        head += 1
        view[col] = node.val
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return [view[c] for c in range(min(view), max(view) + 1)]

Java

public static int[] bottomView(TreeNode root) {
    if (root == null) return new int[0];
    Map<Integer, Integer> view = new HashMap<>();
    List<TreeNode> nodes = new ArrayList<>();
    List<Integer> cols = new ArrayList<>();
    nodes.add(root);
    cols.add(0);
    int lo = 0, hi = 0;
    for (int h = 0; h < nodes.size(); h++) {
        TreeNode node = nodes.get(h);
        int col = cols.get(h);
        view.put(col, node.val);
        lo = Math.min(lo, col);
        hi = Math.max(hi, col);
        if (node.left != null) { nodes.add(node.left); cols.add(col - 1); }
        if (node.right != null) { nodes.add(node.right); cols.add(col + 1); }
    }
    int[] out = new int[hi - lo + 1];
    for (int c = lo; c <= hi; c++) out[c - lo] = view.get(c);
    return out;
}

C++

vector<int> bottomView(TreeNode* root) {
    if (!root) return {};
    map<int, int> view;
    vector<pair<TreeNode*, int>> q = {{root, 0}};
    for (size_t h = 0; h < q.size(); h++) {
        TreeNode* node = q[h].first;
        int col = q[h].second;
        view[col] = node->val;
        if (node->left) q.push_back({node->left, col - 1});
        if (node->right) q.push_back({node->right, col + 1});
    }
    vector<int> out;
    for (auto& kv : view) out.push_back(kv.second);
    return out;
}

JavaScript

var bottomView = function(root) {
    if (root === null) return [];
    var view = {}, lo = 0, hi = 0;
    var nodes = [root], cols = [0], head = 0;
    while (head < nodes.length) {
        var node = nodes[head], col = cols[head];
        head++;
        view[col] = node.val;
        if (col < lo) lo = col;
        if (col > hi) hi = col;
        if (node.left !== null) { nodes.push(node.left); cols.push(col - 1); }
        if (node.right !== null) { nodes.push(node.right); cols.push(col + 1); }
    }
    var out = [];
    for (var c = lo; c <= hi; c++) out.push(view[c]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Breadth-First Search (BFS)