Bottom View of Binary Tree: Methods and Examples

There can be multiple methods to find the bottom view of a binary tree. Let's discuss all of them along with their respective algorithm, example code, and reasons.

1. Using Level Order Traversal (Breadth-First Search)

Level-order traversal is a breadth-first traversal technique where nodes are explored level by level. To perform the bottom view, we will change the level-order traversal in such a way that we recall only the last node encountered at each horizontal distance.

Algorithm

• Do a level-order traversal of the tree.
• Compute the horizontal distance of all nodes from the root. The horizontal distance of the root node is 0.
• Save the value of the node in a map where the horizontal distance is used as the key and the node value is the value.
• Replace the previous value in the map if there is already a node on the map for the given horizontal distance.
• After the traversal is done, the map will have the bottom view of the tree.

Pseudo Code

bottomView(root):
    if root is null:
        return []

    map horizontalDistanceMap
    queue Q = empty queue
    Q.enqueue((root, 0))  // Start with the root at horizontal distance 0

    while Q is not empty:
        node, horizontalDistance = Q.dequeue()
        horizontalDistanceMap[horizontalDistance] = node.value
        
        if node.left:
            Q.enqueue((node.left, horizontalDistance - 1))
        if node.right:
            Q.enqueue((node.right, horizontalDistance + 1))
    
    // Extract the values in the map, sorted by horizontal distance
    result = sorted(horizontalDistanceMap.items())
    return result

C++

#include <iostream>
#include <queue>
#include <map>
#include <vector>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

class Pair {
public:
    Node *node;
    int hd;
    Pair(Node *node, int hd) {
        this->node = node;
        this->hd = hd;
    }
};

vector<int> bottomView(Node *root) {
    if (root == nullptr) return {};

    map<int, int> hdMap; // Map to store HD and the corresponding node data
    queue<Pair> q;
    q.push(Pair(root, 0));

    while (!q.empty()) {
        Pair temp = q.front();
        q.pop();
        Node *curr = temp.node;
        int hd = temp.hd;

        hdMap[hd] = curr->data;

        if (curr->left) q.push(Pair(curr->left, hd - 1));
        if (curr->right) q.push(Pair(curr->right, hd + 1));
    }

    vector<int> result;
    for (auto &entry : hdMap) {
        result.push_back(entry.second);
    }

    return result;
}

int main() {
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(5);
    root->left->right = new Node(3);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);
    root->right->right = new Node(25);

    vector<int> result = bottomView(root);

    for (int i : result) {
        cout << i << " ";
    }

    return 0;
}

Java

import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class Pair {
    Node node;
    int hd;
    Pair(Node node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}

class BottomView {
    static ArrayList<Integer> bottomView(Node root) {
        if (root == null) return new ArrayList<>();

        Map<Integer, Integer> hdMap = new TreeMap<>();
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(root, 0));

        while (!q.isEmpty()) {
            Node curr = q.peek().node;
            int hd = q.peek().hd;
            q.poll();

            hdMap.put(hd, curr.data);

            if (curr.left != null) {
                q.add(new Pair(curr.left, hd - 1));
            }
            if (curr.right != null) {
                q.add(new Pair(curr.right, hd + 1));
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int value : hdMap.values()) {
            result.add(value);
        }
        return result;
    }

    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(5);
        root.left.right = new Node(3);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        ArrayList<Integer> result = bottomView(root);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

from collections import deque

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

def bottomView(root):
    if not root:
        return []

    hdMap = {}
    q = deque([(root, 0)])

    while q:
        node, hd = q.popleft()

        hdMap[hd] = node.data

        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))

    result = []
    for hd in sorted(hdMap.keys()):
        result.append(hdMap[hd])

    return result

# Driver code
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right.right = Node(25)

result = bottomView(root)
print(" ".join(map(str, result)))

Output

5 10 3 14 25

Explanation

• The above code is an implementation of finding the bottom view of a binary tree using level-order traversal (BFS) strategy. 
• It utilizes a queue to keep nodes of each level and a map to keep the latest node at every horizontal distance (HD). 
• The bottom view includes the nodes visible when the tree is observed.

2. Depth First Search (DFS)

In this solution, DFS is utilized to perform the tree traversal and keep track of the depth and horizontal distance (HD) of all nodes. We modify bottom view by finding the maximum depth among nodes at each HD.

Pseudo Code

DFS(node, horizontalDistance, verticalLevel):
    if node is null:
        return
    
    if horizontalDistance not in map:
        map[horizontalDistance] = (verticalLevel, node.value)
    else:
        if verticalLevel >= map[horizontalDistance][0]:
            map[horizontalDistance] = (verticalLevel, node.value)
    
    DFS(node.left, horizontalDistance - 1, verticalLevel + 1)
    DFS(node.right, horizontalDistance + 1, verticalLevel + 1)

C++

#include <iostream>
#include <map>
#include <vector>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

class Pair {
public:
    int data, depth;
    Pair(int data, int depth) {
        this->data = data;
        this->depth = depth;
    }
};

void dfs(Node *root, int hd, int depth, map<int, Pair> &hdMap) {
    if (root == nullptr) return;

    if (hdMap.find(hd) == hdMap.end() || depth >= hdMap[hd].depth) {
        hdMap[hd] = Pair(root->data, depth);
    }

    dfs(root->left, hd - 1, depth + 1, hdMap);
    dfs(root->right, hd + 1, depth + 1, hdMap);
}

vector<int> bottomView(Node *root) {
    map<int, Pair> hdMap;
    dfs(root, 0, 0, hdMap);

    vector<int> result;
    for (auto &entry : hdMap) {
        result.push_back(entry.second.data);
    }

    return result;
}

int main() {
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(5);
    root->left->right = new Node(3);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);
    root->right->right = new Node(25);

    vector<int> result = bottomView(root);

    for (int i : result) {
        cout << i << " ";
    }

    return 0;
}

Java

import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class Pair {
    int data, depth;
    Pair(int data, int depth) {
        this.data = data;
        this.depth = depth;
    }
}

class BottomView {
    static void dfs(Node root, int hd, int depth, Map<Integer, Pair> hdMap) {
        if (root == null) return;

        if (!hdMap.containsKey(hd) || depth >= hdMap.get(hd).depth) {
            hdMap.put(hd, new Pair(root.data, depth));
        }

        dfs(root.left, hd - 1, depth + 1, hdMap);
        dfs(root.right, hd + 1, depth + 1, hdMap);
    }

    static ArrayList<Integer> bottomView(Node root) {
        Map<Integer, Pair> hdMap = new TreeMap<>();
        dfs(root, 0, 0, hdMap);

        ArrayList<Integer> result = new ArrayList<>();
        for (Pair value : hdMap.values()) {
            result.add(value.data);
        }
        return result;
    }

    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(5);
        root.left.right = new Node(3);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        ArrayList<Integer> result = bottomView(root);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

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

def dfs(root, hd, depth, hdMap):
    if not root:
        return

    if hd not in hdMap or depth >= hdMap[hd][1]:
        hdMap[hd] = (root.data, depth)

    dfs(root.left, hd - 1, depth + 1, hdMap)
    dfs(root.right, hd + 1, depth + 1, hdMap)

def bottomView(root):
    hdMap = {}
    dfs(root, 0, 0, hdMap)

    result = []
    for hd in sorted(hdMap.keys()):
        result.append(hdMap[hd][0])

    return result

# Driver code
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right.right = Node(25)

result = bottomView(root)
print(" ".join(map(str, result)))

Output

5 10 3 14 25

Explanation

• Do a DFS, passing the node's HD and depth with every recursive function call.
• If a node is the first for a particular HD or is deeper, put the node's data into the map.
• After DFS, sort HD keys and return bottom view nodes in order.

3. Using Hashing (Breadth-First Search)

This solution uses a HashMap to keep track of the HD as the key and the value of the node as the value. We are going level by level through the tree and updating each node for every HD.

Pseudo Code

Function BottomView(root):
    If root is NULL:
        Return an empty list
    
    Initialize an empty map hdMap to store horizontal distance and node data
    Initialize a stack or queue for DFS/BFS traversal

    Perform DFS or BFS:
        Initialize the horizontal distance (hd) of root as 0
        Push the root into the stack or queue with hd = 0

    While the stack or queue is not empty:
        Pop or dequeue the front node and its horizontal distance (hd)
        Update the map hdMap with hd as the key and node data as the value

        If the node has a left child:
            Push or enqueue the left child with hd - 1
        If the node has a right child:
            Push or enqueue the right child with hd + 1

    For each key in hdMap sorted by hd:
        Add the node data to the result list
    
    Return the result list as the bottom view

Algorithm

• Do a level-order traversal of the tree.
• Use a HashMap with keys being the HDs and values being the node values at those HDs.
• After crossing it, extract the map values. Nodes in every HD will be nodes last seen at every of those locations.

C++

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

vector<int> bottomView(Node *root) {
    if (!root) return {};

    map<int, int> hdMap;
    queue<pair<Node*, int>> q;
    q.push({root, 0});

    while (!q.empty()) {
        Node *curr = q.front().first;
        int hd = q.front().second;
        q.pop();

        hdMap[hd] = curr->data;

        if (curr->left) q.push({curr->left, hd - 1});
        if (curr->right) q.push({curr->right, hd + 1});
    }

    vector<int> result;
    for (auto &entry : hdMap) {
        result.push_back(entry.second);
    }

    return result;
}

int main() {
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(5);
    root->left->right = new Node(3);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);
    root->right->right = new Node(25);

    vector<int> result = bottomView(root);
    for (int i : result) {
        cout << i << " ";
    }

    return 0;
}

Java

import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class BottomView {
    static ArrayList<Integer> bottomView(Node root) {
        if (root == null) return new ArrayList<>();

        Map<Integer, Integer> hdMap = new TreeMap<>();
        Queue<Map.Entry<Node, Integer>> q = new LinkedList<>();
        q.add(new AbstractMap.SimpleEntry<>(root, 0));

        while (!q.isEmpty()) {
            Map.Entry<Node, Integer> entry = q.poll();
            Node curr = entry.getKey();
            int hd = entry.getValue();

            hdMap.put(hd, curr.data);

            if (curr.left != null) q.add(new AbstractMap.SimpleEntry<>(curr.left, hd - 1));
            if (curr.right != null) q.add(new AbstractMap.SimpleEntry<>(curr.right, hd + 1));
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int value : hdMap.values()) {
            result.add(value);
        }
        return result;
    }

    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(5);
        root.left.right = new Node(3);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        ArrayList<Integer> result = bottomView(root);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

from collections import deque

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

def bottomView(root):
    if not root:
        return []

    hdMap = {}
    q = deque([(root, 0)])

    while q:
        node, hd = q.popleft()

        hdMap[hd] = node.data

        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))

    result = []
    for hd in sorted(hdMap.keys()):
        result.append(hdMap[hd])

    return result

# Driver code
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right.right = Node(25)

result = bottomView(root)
print(" ".join(map(str, result)))

Output

5 10 3 14 25

Explanation

• Perform a recursive tree traversal with each node's horizontal distance (HD) and depth.
• Store the deepest node for an HD in a map, replacing it if a deeper node with the identical HD is encountered.
• Retrieve the node values from the map in HD order to obtain the bottom view.

4. Using Queue Approach (BFS)

By the Queue Approach (BFS), we do a level-order traversal of the tree, keeping an eye on each node's horizontal distance and noting the deepest node at every horizontal distance.

Algorithm

• Build a queue and a map to hold nodes and their horizontal distance (HD) as well as node data.
• Add the root node with HD 0 and build the map to keep the node info at every HD.
• While the queue is not empty, dequeue the node and add its info to the map at the corresponding HD.
• Add its left child and right child with new HDs.
• After BFS, the map will hold the last node at every HD.
• Sort the map by HD and gather the node data to create the bottom view.
• Return the result list that is the bottom view of the tree.

Pseudo Code

function bottomView(root):
    if root is null:
        return []

    Create an empty map hdMap
    Create an empty queue q
    Enqueue root with horizontal distance 0

    while q is not empty:
        node, hd = dequeue q
        hdMap[hd] = node.data
        
        if node.left is not null:
            enqueue node.left with hd - 1
        if node.right is not null:
            enqueue node.right with hd + 1
    
    Create an empty list result
    for each hd in hdMap, in sorted order:
        append hdMap[hd] to result
    
    return result

C++

#include <iostream>
#include <queue>
#include <map>
#include <vector>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

class Pair {
public:
    Node *node;
    int hd;
    Pair(Node *node, int hd) {
        this->node = node;
        this->hd = hd;
    }
};

vector<int> bottomView(Node *root) {
    if (root == nullptr) return {};

    map<int, int> hdMap; // Map to store HD and the corresponding node data
    queue<Pair> q;
    q.push(Pair(root, 0));

    while (!q.empty()) {
        Pair temp = q.front();
        q.pop();
        Node *curr = temp.node;
        int hd = temp.hd;

        hdMap[hd] = curr->data;  // Update the map with the current node

        if (curr->left) q.push(Pair(curr->left, hd - 1));  // Left child at HD - 1
        if (curr->right) q.push(Pair(curr->right, hd + 1));  // Right child at HD + 1
    }

    vector<int> result;
    for (auto &entry : hdMap) {
        result.push_back(entry.second);  // Add node data to the result in order of HD
    }

    return result;
}

int main() {
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(5);
    root->left->right = new Node(3);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);
    root->right->right = new Node(25);

    vector<int> result = bottomView(root);
    for (int i : result) {
        cout << i << " ";
    }

    return 0;
}

Java

import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class Pair {
    Node node;
    int hd;
    Pair(Node node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}

class BottomView {
    static ArrayList<Integer> bottomView(Node root) {
        if (root == null) return new ArrayList<>();

        Map<Integer, Integer> hdMap = new TreeMap<>();
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(root, 0));

        while (!q.isEmpty()) {
            Node curr = q.peek().node;
            int hd = q.peek().hd;
            q.poll();

            hdMap.put(hd, curr.data);

            if (curr.left != null) {
                q.add(new Pair(curr.left, hd - 1));
            }
            if (curr.right != null) {
                q.add(new Pair(curr.right, hd + 1));
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int value : hdMap.values()) {
            result.add(value);
        }
        return result;
    }

    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(5);
        root.left.right = new Node(3);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        ArrayList<Integer> result = bottomView(root);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

from collections import deque

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

def bottomView(root):
    if not root:
        return []

    hdMap = {}  # Map to store horizontal distance and node data
    q = deque([(root, 0)])

    while q:
        curr, hd = q.popleft()

        # Update map with the most recent node at each horizontal distance
        hdMap[hd] = curr.data

        if curr.left:
            q.append((curr.left, hd - 1))
        if curr.right:
            q.append((curr.right, hd + 1))

    # Extract the bottom view from the map in sorted order of horizontal distance
    return [hdMap[hd] for hd in sorted(hdMap.keys())]

# Driver code
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right.right = Node(25)

result = bottomView(root)
print(" ".join(map(str, result)))

Output

5 10 3 14 25

Explanation

• The tree is traversed level by level with the help of a queue, keeping each node's data and horizontal distance (HD) in a map. A node's data is refreshed if a node is visited at the same HD.
• The root is at HD 0. Left children decrease HD by 1, and the right children increase HD by 1. Nodes are kept in the map based on HD and refreshed for each HD.
• Upon traversing, the map is traversed by HDs in sequence, aggregating node values for the bottom view, and is returned as the output.

Time and Space Complexity

In conclusion, bottom view of binary tree offers us a different view of the tree structure and can be calculated by many algorithms like level-order traversal, depth-first search, hashing, hashmap and queue. All the techniques assign horizontal distances with nodes and ensure the bottom-most node of each horizontal distance is added in final output. Each of these approaches has its own advantage, with level-order traversal introducing convenience, DFS ensures flexibility, and making the solution convenient.

1. Can we utilize the other tree traversals in finding the bottom view?

Yes, BFS and DFS may also be applied. All algorithms entail maintaining nodes at various horizontal distances and keeping the node last reached chosen for every distance.

2. What is the time complexity of the level-order traversal method?

The level-order traversal method has a time complexity of O(N), with N being the number of nodes in the binary tree.

3. Why is it difficult to calculate the bottom view?

The biggest challenge in bottom view computation is dealing with the horizontal distance and ensuring only the bottom-most node at each horizontal distance is visited. Dealing with it during DFS and BFS properly can be cumbersome without proper data structures.