Table of contents

Bottom view of a Binary Tree

Given a binary tree, write a program to print its bottom view. The bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom. Nodes are visible based on their horizontal distance from the root node. If two nodes have the same horizontal distance, the one that is lower in the tree appears in the bottom view.

Input/Output Examples

plaintext
Example 1:
Input:

     1
    / \
   2   3
  / \   \
 4   5   6

Output:
[4, 2, 5, 3, 6]
Explanation: The bottom view consists of nodes 4, 2, 5, 3, and 6.

Example 2:
Input:

     20
    /  \
   8   22
  / \    \
 5  10    25
    /  \
   14   12

Output:
[5, 14, 10, 12, 25]
Explanation: The bottom view consists of nodes 5, 14, 10, 12, and 25.

Approach to Print the Bottom View of a Binary Tree

  1. Level Order Traversal with Horizontal Distance:
    • We perform a level-order traversal (BFS) of the tree, using a queue. Along with each node, we keep track of its horizontal distance from the root.
    • The root node is considered to be at horizontal distance 0. For each left child, the horizontal distance decreases by 1, and for each right child, it increases by 1.
  2. Store the Bottom View in a Map:
    • Use a map (or dictionary) to store the last node encountered at each horizontal distance. The key of the map is the horizontal distance, and the value is the node's value.
    • During traversal, update the map for every node visited, which ensures that only the bottom-most node at each horizontal distance is stored.
  3. Extract and Print the Bottom View:
    • After completing the level-order traversal, extract the values from the map sorted by the horizontal distance and print them.

C++ Program to Print the Bottom View of a Binary Tree

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

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Structure to store a node with its horizontal distance
struct NodeInfo {
    TreeNode* node;
    int horizontalDistance;

    NodeInfo(TreeNode* n, int hd) : node(n), horizontalDistance(hd) {}
};

// Function to print the bottom view of a binary tree
void bottomView(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    // Map to store the last node at each horizontal distance
    map<int, int> hdNodeMap;

    // Queue for level-order traversal, storing node and horizontal distance
    queue<NodeInfo> q;
    q.push(NodeInfo(root, 0));

    while (!q.empty()) {
        NodeInfo curr = q.front();
        q.pop();

        // Update the map with the current node for this horizontal distance
        hdNodeMap[curr.horizontalDistance] = curr.node->data;

        // Traverse the left child with horizontal distance -1
        if (curr.node->left) {
            q.push(NodeInfo(curr.node->left, curr.horizontalDistance - 1));
        }

        // Traverse the right child with horizontal distance +1
        if (curr.node->right) {
            q.push(NodeInfo(curr.node->right, curr.horizontalDistance + 1));
        }
    }

    // Print the bottom view (nodes stored in map sorted by horizontal distance)
    for (auto it : hdNodeMap) {
        cout << it.second << " ";
    }
    cout << endl;
}

int main() {
    // Create a sample tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    // Print the bottom view of the tree
    bottomView(root);

    return 0;
}

Java Program to Print the Bottom View of a Binary Tree

java
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;
import java.util.LinkedList;

// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

// Structure to store a node with its horizontal distance
class NodeInfo {
    TreeNode node;
    int horizontalDistance;

    NodeInfo(TreeNode n, int hd) {
        node = n;
        horizontalDistance = hd;
    }
}

public class BottomViewBinaryTree {

    // Function to print the bottom view of a binary tree
    public static void bottomView(TreeNode root) {
        if (root == null) {
            return;
        }

        // TreeMap to store the last node at each horizontal distance (sorted by HD)
        Map<Integer, Integer> hdNodeMap = new TreeMap<>();

        // Queue for level-order traversal, storing node and horizontal distance
        Queue<NodeInfo> queue = new LinkedList<>();
        queue.add(new NodeInfo(root, 0));

        while (!queue.isEmpty()) {
            NodeInfo curr = queue.poll();

            // Update the map with the current node for this horizontal distance
            hdNodeMap.put(curr.horizontalDistance, curr.node.data);

            // Traverse the left child with horizontal distance -1
            if (curr.node.left != null) {
                queue.add(new NodeInfo(curr.node.left, curr.horizontalDistance - 1));
            }

            // Traverse the right child with horizontal distance +1
            if (curr.node.right != null) {
                queue.add(new NodeInfo(curr.node.right, curr.horizontalDistance + 1));
            }
        }

        // Print the bottom view (nodes stored in map sorted by horizontal distance)
        for (int node : hdNodeMap.values()) {
            System.out.print(node + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a sample tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        // Print the bottom view of the tree
        bottomView(root);
    }
}

Python Program to Print the Bottom View of a Binary Tree

python
from collections import deque

# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Structure to store a node with its horizontal distance
class NodeInfo:
    def __init__(self, node, horizontal_distance):
        self.node = node
        self.horizontal_distance = horizontal_distance

# Function to print the bottom view of a binary tree
def bottom_view(root):
    if root is None:
        return

    # Dictionary to store the last node at each horizontal distance
    hd_node_map = {}

    # Queue for level-order traversal, storing node and horizontal distance
    queue = deque([NodeInfo(root, 0)])

    while queue:
        curr = queue.popleft()

        # Update the map with the current node for this horizontal distance
        hd_node_map[curr.horizontal_distance] = curr.node.data

        # Traverse the left child with horizontal distance -1
        if curr.node.left:
            queue.append(NodeInfo(curr.node.left, curr.horizontal_distance - 1))

        # Traverse the right child with horizontal distance +1
        if curr.node.right:
            queue.append(NodeInfo(curr.node.right, curr.horizontal_distance + 1))

    # Print the bottom view (nodes stored in map sorted by horizontal distance)
    for hd in sorted(hd_node_map):
        print(hd_node_map[hd], end=" ")
    print()

# Example usage
if __name__ == "__main__":
    # Create a sample tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)

    # Print the bottom view of the tree
    bottom_view(root)
  • Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once during the level-order traversal.
  • Space Complexity: O(n) because we store information for each node in a queue and a map. In the worst case, the queue and map may store information for all n nodes.

DSA

Related Articles