Bottom View of Binary Tree in DSA Typescript - Build from Scratch

Bottom View of Binary Tree

📖 Scenario: Imagine you are working on a program that helps visualize a binary tree from different angles. One useful view is the bottom view, which shows the nodes visible when looking at the tree from below.Each node in the tree has a horizontal distance from the root. The bottom view shows the last node at each horizontal distance when viewed from the bottom.

🎯 Goal: You will build a TypeScript program that finds the bottom view of a given binary tree. The program will print the node values visible from the bottom, ordered from left to right.

📋 What You'll Learn

Create a binary tree with the exact structure given.

Use a variable to track horizontal distances.

Implement the logic to find the bottom view using a queue and a map.

Print the bottom view nodes in order from leftmost to rightmost horizontal distance.

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree is useful in graphical representations, network routing visualizations, and understanding hierarchical data from different perspectives.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a class called Node with data (number), left (Node or null), and right (Node or null). Then create the binary tree with this exact structure:
20
/ \
8 22
/ \ \
5 3 25
/ \
10 14

DSA Typescript

// Define Node class and create the tree nodes
// Your code here

Hint

Define the Node class with data, left, and right. Then create the nodes exactly as shown to build the tree.

2

Set Up a Map to Track Bottom View Nodes

Create a Map called hdNodeMap to store the latest node data for each horizontal distance (number). Also create a queue array to hold pairs of Node and its horizontal distance (number). Initialize the queue with the root node and horizontal distance 0.

DSA Typescript

class Node {
    data: number;
    left: Node | null;
    right: Node | null;
    constructor(data: number) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

const 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.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

// Create map and queue for bottom view
// Your code here

Hint

Use a Map to store horizontal distance keys and node data values. Use a queue array to hold objects with node and hd properties.

3

Implement Bottom View Logic Using Level Order Traversal

Use a while loop to process nodes in queue. For each node, update hdNodeMap with the node's data for its horizontal distance. Add the left child to the queue with horizontal distance minus 1, and the right child with horizontal distance plus 1, if they exist.

DSA Typescript

class Node {
    data: number;
    left: Node | null;
    right: Node | null;
    constructor(data: number) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

const 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.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

const hdNodeMap = new Map();
const queue: Array = [];
queue.push({node: root, hd: 0});

// Implement the bottom view traversal logic below
// Your code here

Hint

Use a while loop to remove nodes from the queue. Update the map with the current node's data for its horizontal distance. Add children with updated horizontal distances.

4

Print the Bottom View Nodes from Left to Right

Extract the keys from hdNodeMap, sort them in ascending order, then print the corresponding node data values separated by spaces on one line.

DSA Typescript

class Node {
    data: number;
    left: Node | null;
    right: Node | null;
    constructor(data: number) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

const 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.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

const hdNodeMap = new Map();
const queue: Array = [];
queue.push({node: root, hd: 0});

while (queue.length > 0) {
    const {node, hd} = queue.shift()!;
    hdNodeMap.set(hd, node.data);
    if (node.left !== null) {
        queue.push({node: node.left, hd: hd - 1});
    }
    if (node.right !== null) {
        queue.push({node: node.right, hd: hd + 1});
    }
}

// Print the bottom view nodes in order
// Your code here

Hint

Sort the horizontal distances and print the corresponding node data values separated by spaces.