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.

Practice

1. What does the bottom view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the right side

B. Nodes visible when the tree is viewed from the top

C. Nodes visible when the tree is viewed from the bottom

D. Nodes visible when the tree is viewed from the left side

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes visible when looking at the tree from below, meaning the lowest nodes at each horizontal distance.

2. Step 2: Compare with other views

   Top view shows nodes from above, left and right views show nodes from sides, so bottom view is unique for bottom perspective.

3. Final Answer:

   Nodes visible when the tree is viewed from the bottom -> Option C

4. Quick Check:

   Bottom view = nodes visible from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal distance [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking bottom view shows all leaf nodes
• Mixing bottom view with side views

2. Which of the following JavaScript code snippets correctly initializes a Map to store horizontal distances and nodes for bottom view?

easy

A. const map = new Map();

B. const map = {};

C. const map = new Array();

D. const map = new Set();

Solution

1. Step 1: Identify suitable data structure for key-value pairs

   Map is ideal for storing horizontal distance as key and node data as value with easy insertion and retrieval.

2. Step 2: Check other options

   Object ({}) can be used but Map is preferred for ordered keys and better methods; Array and Set are not suitable for key-value pairs.

3. Final Answer:

   const map = new Map(); -> Option A

4. Quick Check:

   Use Map for horizontal distance mapping [OK]

Hint: Use Map() for key-value storage in bottom view [OK]

Common Mistakes:

• Using Array instead of Map for key-value pairs
• Using Set which stores only unique values, not key-value
• Using plain object without considering key types

3. Consider the following binary tree and code snippet to print its bottom view:

class Node {
  constructor(data) {
    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);

// Bottom view logic omitted for brevity
// Assume correct implementation

// Output bottom view nodes in order of horizontal distance
// What is the bottom view output?

medium

A. [5, 8, 3, 14, 25]

B. [5, 10, 3, 14, 25]

C. [5, 10, 3, 22, 25]

D. [8, 10, 3, 14, 25]

Solution

1. Step 1: Assign horizontal distances and track bottom nodes

   Assign horizontal distances: 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(-1), 14(1). Bottom view keeps last node at each horizontal distance.

2. Step 2: Determine bottom nodes at each horizontal distance

   At -2: 5; at -1: 10 (overwrites 8); at 0: 3 (overwrites 20); at 1: 14 (overwrites 22); at 2: 25.

3. Final Answer:

   [5, 10, 3, 14, 25] -> Option B

4. Quick Check:

   Bottom view nodes = [5,10,3,14,25] [OK]

Hint: Track last node at each horizontal distance [OK]

Common Mistakes:

• Using first node instead of last at horizontal distance
• Mixing horizontal distances incorrectly
• Ignoring overwriting nodes at same horizontal distance

4. The following code attempts to print the bottom view of a binary tree but produces incorrect output. What is the main issue?

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

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

  return Array.from(map.values());
}

medium

A. It stores only the first node at each horizontal distance, not the bottom-most

B. It uses shift() which is inefficient for queue

C. It does not handle null root input

D. It uses Map instead of Object for storage

Solution

1. Step 1: Analyze map update condition

   The code sets map value only if horizontal distance key is not present, so it keeps first node encountered at that hd.

2. Step 2: Understand bottom view requirement

   Bottom view requires last node at each horizontal distance (lowest level), so map should update value every time a node at same hd is found.

3. Final Answer:

   It stores only the first node at each horizontal distance, not the bottom-most -> Option A

4. Quick Check:

   Bottom view needs last node per hd, code keeps first [OK]

Hint: Update map value for every node at horizontal distance [OK]

Common Mistakes:

• Not updating map on repeated horizontal distances
• Confusing top view logic with bottom view
• Ignoring queue inefficiency but that doesn't affect correctness

5. Given a binary tree where multiple nodes share the same horizontal distance and level, how should the bottom view algorithm decide which node to display?

hard

A. Display the node with the smallest value at that horizontal distance

B. Display the leftmost node at that horizontal distance and level

C. Display the rightmost node at that horizontal distance and level

D. Display the node encountered last in level order traversal at that horizontal distance

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, bottom view shows the one visible from bottom, which is the one encountered last in level order traversal.

2. Step 2: Reason about traversal order

   Level order traversal processes nodes left to right at each level, so last encountered node at hd and level overwrites previous.

3. Final Answer:

   Display the node encountered last in level order traversal at that horizontal distance -> Option D

4. Quick Check:

   Bottom view uses last node in level order per hd [OK]

Hint: Use last node in level order traversal for bottom view [OK]

Common Mistakes:

• Choosing leftmost or rightmost arbitrarily
• Choosing node by value instead of position
• Ignoring traversal order impact