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

Bottom View of Binary Tree

📖 Scenario: Imagine you have a tree of family members standing in a garden. You want to see who is visible if you look at the tree from the bottom. Some members might be hidden behind others. We will find out which members are visible from the bottom view of the tree.

🎯 Goal: Build a program that finds the bottom view of a binary tree. The bottom view shows the nodes visible when the tree is seen from below.

📋 What You'll Learn

Create a binary tree using nodes with value, left, and right properties

Use a variable to track horizontal distances of nodes

Traverse the tree to find the bottom view nodes

Print the bottom view nodes in order from left to right

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree helps in understanding which elements are visible from a certain perspective, useful in graphical applications and visualization tools.

💼 Career

Understanding tree traversals and views is important for software engineers working with hierarchical data, UI rendering, and spatial data structures.

1

Create the binary tree nodes

Create a binary tree with a root node called root. The root node should have value 20, a left child with value 8, and a right child with value 22. The left child of 8 should be 5, and the right child of 8 should be 3. The right child of 3 should be 14, and the left child of 3 should be 10.

DSA Javascript

// Create the binary tree nodes with the exact values and structure
// Your code here

Hint

Define a Node class with value, left, and right. Then create nodes and link them exactly as described.

2

Set up a map to track horizontal distances

Create a variable called hdMap as an empty Map to store nodes by their horizontal distance. Also create a queue called queue as an empty array to help with level order traversal. Add an object with node as root and hd (horizontal distance) as 0 to the queue.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        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.left.right.left = new Node(10);
root.left.right.right = new Node(14);

// Create hdMap and queue for traversal
// Your code here

Hint

Use a Map to store nodes by horizontal distance and an array as a queue for level order traversal. Start by adding the root with horizontal distance 0.

3

Traverse the tree to find bottom view nodes

Use a while loop that runs while queue.length > 0. Inside the loop, remove the first element from queue into a variable called temp. Update hdMap at key temp.hd with temp.node.value to keep the bottom-most node at that horizontal distance. If temp.node.left exists, add it to queue with horizontal distance temp.hd - 1. If temp.node.right exists, add it to queue with horizontal distance temp.hd + 1.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        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.left.right.left = new Node(10);
root.left.right.right = new Node(14);

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

// Traverse the tree to fill hdMap with bottom view nodes
// Your code here

Hint

Use a queue to visit nodes level by level. Update the map with the latest node at each horizontal distance. Add children with updated horizontal distances to the queue.

4

Print the bottom view nodes from left to right

Create an array called sortedKeys by sorting the keys of hdMap in ascending order. Use a for loop to iterate over sortedKeys and print the corresponding values from hdMap separated by spaces on one line.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        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.left.right.left = new Node(10);
root.left.right.right = new Node(14);

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

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

// Print the bottom view nodes from left to right
// Your code here

Hint

Sort the horizontal distances and print the stored node values in order separated by spaces.