Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Trees

Bottom View of a Binary Tree

Medium · Trees · Asked at Amazon, Microsoft, Flipkart, Paytm

Columns are numbered as in the top view (root 0, left child −1, right child +1). The bottom view shows, for every column from left to right, the node of that column that comes last in level order (so a deeper node wins, and within the same level the one further right wins).

Input

First line: k. Second line: k values — the tree in level order, -1 means no node.

Output

The bottom view from the leftmost column to the rightmost, space-separated.

Constraints

BFS carrying the column number; always overwrite the value stored for the column.

Example 1

Input

11
20 8 22 5 3 -1 25 -1 -1 10 14

Output

5 10 3 14 25

Example 2

Input

7
1 2 3 4 5 6 7

Output

4 2 6 3 7

Hints

  1. Use the same column numbering as the top view.
  2. Traverse in level order and always overwrite the value stored for a column — the last write is the lowest (and, at equal depth, rightmost) node.

Approach

BFS with (node, column) pairs, storing column → value and overwriting on every visit. Since BFS visits deeper levels later and, within a level, goes left to right, the surviving value is the last node in level order for that column. Print columns in increasing order.

Complexity: O(n log n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *left = nullptr, *right = nullptr;
    Node(long long v) : val(v) {}
};

// Build a tree from level order where -1 means "no node".
Node *readTree() {
    int k;
    cin >> k;
    vector<long long> v(k);
    for (auto &x : v) cin >> x;
    if (k == 0 || v[0] == -1) return nullptr;
    Node *root = new Node(v[0]);
    queue<Node *> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < k) {
        Node *cur = q.front();
        q.pop();
        if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
        i++;
        if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
        i++;
    }
    return root;
}

int main() {
    Node *root = readTree();
    map<int, long long> last;
    queue<pair<Node *, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        Node *n = q.front().first;
        int c = q.front().second;
        q.pop();
        last[c] = n->val;
        if (n->left) q.push({n->left, c - 1});
        if (n->right) q.push({n->right, c + 1});
    }
    bool sp = false;
    for (auto &e : last) cout << (sp ? " " : "") << e.second, sp = true;
    cout << "\n";
    return 0;
}

Python solution

import sys
from collections import deque

sys.setrecursionlimit(100000)

class Node:
    def __init__(self, val):
        self.val, self.left, self.right = val, None, None


def build_tree(v):
    """Build a tree from level order where -1 means "no node"."""
    if not v or v[0] == -1:
        return None
    root = Node(v[0])
    q, i = deque([root]), 1
    while q and i < len(v):
        cur = q.popleft()
        if i < len(v) and v[i] != -1:
            cur.left = Node(v[i])
            q.append(cur.left)
        i += 1
        if i < len(v) and v[i] != -1:
            cur.right = Node(v[i])
            q.append(cur.right)
        i += 1
    return root


data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]

last, q = {}, deque([(root, 0)])
while q:
    n, c = q.popleft()
    last[c] = n.val
    if n.left:
        q.append((n.left, c - 1))
    if n.right:
        q.append((n.right, c + 1))
print(*[last[c] for c in sorted(last)])

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node left, right;
        Node(long v) { val = v; }
    }

    // Build a tree from level order where -1 means "no node".
    static Node readTree(Scanner sc) {
        int k = sc.nextInt();
        long[] v = new long[k];
        for (int i = 0; i < k; i++) v[i] = sc.nextLong();
        if (k == 0 || v[0] == -1) return null;
        Node root = new Node(v[0]);
        ArrayDeque<Node> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < k) {
            Node cur = q.poll();
            if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
            i++;
            if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Node root = readTree(new Scanner(System.in));
        TreeMap<Integer, Long> last = new TreeMap<>();
        ArrayDeque<Object[]> q = new ArrayDeque<>();
        q.add(new Object[] {root, 0});
        while (!q.isEmpty()) {
            Object[] t = q.poll();
            Node n = (Node) t[0];
            int c = (Integer) t[1];
            last.put(c, n.val);
            if (n.left != null) q.add(new Object[] {n.left, c - 1});
            if (n.right != null) q.add(new Object[] {n.right, c + 1});
        }
        StringBuilder sb = new StringBuilder();
        for (long v : last.values()) sb.append(sb.length() > 0 ? " " : "").append(v);
        System.out.println(sb);
    }
}

Solve Bottom View of a Binary Tree online · All practice problems