Printing the Bottom View of a Binary Tree involves displaying the nodes visible when the tree is viewed from below. To Print Bottom View of Binary Tree, at each horizontal distance ie from left to right, the bottom-most node encountered in the tree is considered part of the bottom view.

Code Flow for Print Bottom View of Binary Tree

1. Edge Case:

   • If the tree is empty (root == null), the method prints "the root is null" and exits.

2. Initialization:

   • A TreeMap (map) is created to store nodes by their horizontal distance.

   • A queue is created and the root node is added to it with hrzDis = 0.

3. Level Order Traversal (While Loop):

   • The queue processes one node at a time:

     • Remove (poll) the front node from the queue.

     • Retrieve the node's horizontal distance (hrzDis).

     • Update the TreeMap:

       • Add/Update the node's data in the TreeMap for the current horizontal distance (this ensures the bottom-most node at that hrzDis is recorded).

     • Process Children:

       • Add the left child to the queue with hrzDis - 1.

       • Add the right child to the queue with hrzDis + 1.

4. Print the Bottom View:

   • Iterate over the TreeMap in ascending order of horizontal distances.

   • Print the values stored in the map.

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

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

@Data
class Node {
    int data;
    int hrzDis;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinarySearchTree {
    Node root;

    public static void bottomView(Node root) {
        System.out.println("the root is null");
        if (Objects.isNull(root)) {
            return;
        }
        int hrzDis = 0;
        /*  A TreeMap to store nodes by their horizontal distance. */
        Map<Integer, Integer> map = new TreeMap<>();
        // First add nodes in Queue for level order traversal
        Queue<Node> queue = new LinkedList<>();
        // Assign initialized horizontal distance value to root node and add it to the queue.
        root.hrzDis = hrzDis;
        queue.add(root);
        while (!queue.isEmpty()) {
            /*  Remove (poll) the front node from the queue.    */
            Node node = queue.remove();
            /*  Retrieve the node's horizontal distance (hrzDis).   */
            hrzDis = node.hrzDis;
            /*  Add or Update the node's data in the TreeMap for the current horizontal distance; this ensures the bottom-most node at that hrzDis is recorded.   */
            map.put(hrzDis, node.data);
            // add left child in the queue with horizontal distance hrzDis-1.
            if (Objects.nonNull(node.left)) {
                node.left.hrzDis = hrzDis - 1;
                queue.add(node.left);
            }
            // add right child in the queue with horizontal distance hrzDis+1.
            if (Objects.nonNull(node.right)) {
                node.right.hrzDis = hrzDis + 1;
                queue.add(node.right);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.print("[" + entry.getValue() + "]");
        }
    }

    void insert(int data) {
        System.out.println("BinarySearchTree.insert data = " + data);
        root = insert(root, data);
    }

    Node insert(Node root, int data) {
        if (Objects.isNull(root)) {
            Node tempNode = new Node(data);
            return tempNode;
        }
        if (data > root.data) {
            root.right = insert(root.right, data);
        } else {
            root.left = insert(root.left, data);
        }
        return root;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

public class BinarySearchTreeTest {
    @Test
    void testBottomViewSingleNode() {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        BinarySearchTree.bottomView(tree.root);
//   Expect output: "10"
    }

    @Test
    void testBottomViewBalancedTree() {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(3);
        tree.insert(7);
        tree.insert(12);
        tree.insert(20);
        BinarySearchTree.bottomView(tree.root);
//   Expect output: "3 5 12 15 20"
    }

    @Test
    void testBottomViewLeftSkewedTree() {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        tree.insert(9);
        tree.insert(8);
        tree.insert(7);
        BinarySearchTree.bottomView(tree.root);
//   Expect output: "7 8 9 10"
    }

    @Test
    void testBottomViewRightSkewedTree() {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        tree.insert(11);
        tree.insert(12);
        tree.insert(13);
        BinarySearchTree.bottomView(tree.root);
//   Expect output: "10 11 12 13"
    }

    @Test
    void testBottomViewComplexTree() {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(2);
        tree.insert(7);
        tree.insert(6);
        tree.insert(8);
        tree.insert(20);
        BinarySearchTree.bottomView(tree.root);
//   Expect output: "2 6 7 8 20"
    }

    @Test
    void testBottomViewEmptyTree() {
        BinarySearchTree tree = new BinarySearchTree();
        BinarySearchTree.bottomView(tree.root);
//   Expect output: ""
    }

    @Test
    void testBottomViewUnbalancedTree() {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(4);
        tree.insert(3);
        tree.insert(20);
        tree.insert(18);
        BinarySearchTree.bottomView(tree.root);
//   Expect output: "3 4 5 10 18 20"
    }


    @Test
    void bottomViewTest() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(4);
        binarySearchTree.insert(2);
        binarySearchTree.insert(1);
        binarySearchTree.insert(3);
        binarySearchTree.insert(6);
        binarySearchTree.insert(5);
        binarySearchTree.insert(7);
        binarySearchTree.insert(7);
        BinarySearchTree.bottomView(binarySearchTree.root);
        //   Expect output: "1 2 5 7 7"
    }
}

plugins {
    id("java")
    id("io.freefair.lombok") version "8.13"
}

group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"

repositories {
    mavenCentral()
}

dependencies {
    testImplementation(platform("org.junit:junit-bom:5.10.0"))
    testImplementation("org.junit.jupiter:junit-jupiter")
}

tasks.test {
    useJUnitPlatform()
}

Complexity Analysis

Time Complexity

1. Traversal: Each node is visited once → O(n), where n is the number of nodes.

2. TreeMap Operations: Insert/update operations in the TreeMap take O(log k), where k is the number of unique horizontal distances (≤ n).

Overall: O(n log k).

Space Complexity

1. Queue: Stores nodes at each level of the tree → O(w), where w is the maximum width of the tree.

2. TreeMap: Stores one entry per horizontal distance → O(k), where k is the number of unique horizontal distances.

Overall: O(n).