Top View of Binary Tree in DSA Rust - Execution Trace

Concept Flow - Top View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Traverse tree level by level

↓

For each node:

↓

Check if horizontal distance seen before?

↓

Add node to top view

↓

Ignore node

↓

Add left child with hd-1

↓

Add right child with hd+1

↓

Repeat until all nodes visited

↓

Print nodes in order of horizontal distance

Traverse the tree level by level, track horizontal distances, and record the first node at each horizontal distance to get the top view.

Execution Sample

DSA Rust

use std::collections::{VecDeque, HashMap};

#[derive(Clone)]
struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn print_top_view(root: Option<Box<Node>>) {
    if root.is_none() {
        return;
    }
    let mut queue: VecDeque<(Option<Box<Node>>, i32)> = VecDeque::new();
    let mut map: HashMap<i32, i32> = HashMap::new();
    queue.push_back((root, 0));
    while let Some((node_opt, hd)) = queue.pop_front() {
        let node = node_opt.as_ref().unwrap();
        if !map.contains_key(&hd) {
            map.insert(hd, node.val);
        }
        if let Some(ref left) = node.left {
            queue.push_back((Some(left.clone()), hd - 1));
        }
        if let Some(ref right) = node.right {
            queue.push_back((Some(right.clone()), hd + 1));
        }
    }
    let mut keys: Vec<i32> = map.keys().cloned().collect();
    keys.sort();
    for k in keys {
        println!("{}", map[&k]);
    }
}

// Usage example (tree building omitted for brevity):
// let top_view = print_top_view(build_sample_tree());
// Outputs: 4 2 1 3 7

This code traverses the binary tree using BFS, tracks the first node at each horizontal distance, and prints the top view nodes in left-to-right order.

Execution Table

Step	Operation	Current Node (val)	Horizontal Distance (hd)	Top View Map (hd -> val)	Queue State (node, hd)	Visual State
1	Start at root	1	0	{}	[(1,0)]	1(0)
2	Dequeue node	1	0	{}	[]	1(0)
3	Add node to top view	1	0	{0:1}	[]	1(0)
4	Enqueue left child	2	-1	{0:1}	[(2,-1)]	2(-1) <- 1(0)
5	Enqueue right child	3	1	{0:1}	[(2,-1),(3,1)]	2(-1) <- 1(0) -> 3(1)
6	Dequeue node	2	-1	{0:1}	[(3,1)]	2(-1) <- 1(0) -> 3(1)
7	Add node to top view	2	-1	{-1:2,0:1}	[(3,1)]	2(-1) <- 1(0) -> 3(1)
8	Enqueue left child	4	-2	{-1:2,0:1}	[(3,1),(4,-2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1)
9	Enqueue right child	5	0	{-1:2,0:1}	[(3,1),(4,-2),(5,0)]	4(-2) <- 2(-1) <- 1(0) -> 3(1)
10	Dequeue node	3	1	{-1:2,0:1}	[(4,-2),(5,0)]	4(-2) <- 2(-1) <- 1(0) -> 3(1)
11	Add node to top view	3	1	{-1:2,0:1,1:3}	[(4,-2),(5,0)]	4(-2) <- 2(-1) <- 1(0) -> 3(1)
12	Enqueue left child	6	0	{-1:2,0:1,1:3}	[(4,-2),(5,0),(6,0)]	4(-2) <- 2(-1) <- 1(0) -> 3(1)
13	Enqueue right child	7	2	{-1:2,0:1,1:3}	[(4,-2),(5,0),(6,0),(7,2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
14	Dequeue node	4	-2	{-1:2,0:1,1:3}	[(5,0),(6,0),(7,2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
15	Add node to top view	4	-2	{-2:4,-1:2,0:1,1:3}	[(5,0),(6,0),(7,2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
16	Dequeue node	5	0	{-2:4,-1:2,0:1,1:3}	[(6,0),(7,2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
17	Node at hd=0 already in top view, ignore	5	0	{-2:4,-1:2,0:1,1:3}	[(6,0),(7,2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
18	Dequeue node	6	0	{-2:4,-1:2,0:1,1:3}	[(7,2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
19	Node at hd=0 already in top view, ignore	6	0	{-2:4,-1:2,0:1,1:3}	[(7,2)]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
20	Dequeue node	7	2	{-2:4,-1:2,0:1,1:3}	[]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
21	Add node to top view	7	2	{-2:4,-1:2,0:1,1:3,2:7}	[]	4(-2) <- 2(-1) <- 1(0) -> 3(1) -> 7(2)
22	Queue empty, traversal complete	-	-	{-2:4,-1:2,0:1,1:3,2:7}	[]	Top view nodes: 4, 2, 1, 3, 7

💡 Queue is empty, all nodes visited, top view map complete

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
Queue	[(1,0)]	[]	[(2,-1),(3,1)]	[(3,1)]	[(3,1),(4,-2),(5,0)]	[(4,-2),(5,0)]	[(5,0),(6,0),(7,2)]	[(6,0),(7,2)]	[]
Top View Map	{}	{0:1}	{0:1}	{-1:2,0:1}	{-1:2,0:1}	{-2:4,-1:2,0:1}	{-2:4,-1:2,0:1,1:3}	{-2:4,-1:2,0:1,1:3}	{-2:4,-1:2,0:1,1:3,2:7}

Key Moments - 3 Insights

Why do we only add the first node we see at each horizontal distance to the top view?

Because the top view shows the nodes visible from above, only the first node encountered at each horizontal distance (closest to root level) is visible. Later nodes at the same horizontal distance are hidden behind.

Why do we use a queue and level order traversal instead of DFS?

Level order traversal ensures we visit nodes level by level from top to bottom. This way, the first node at each horizontal distance is guaranteed to be the topmost node, which is needed for the top view.

What does the horizontal distance represent and how is it updated?

Horizontal distance (hd) is an integer representing the horizontal position relative to the root (hd=0). Left child has hd-1, right child has hd+1. This helps group nodes vertically for the top view.

Visual Quiz - 3 Questions

Look at the execution table, what is the top view map after step 15?

A {-2:4, -1:2, 0:1}

B {-2:4, -1:2, 0:1, 1:3}

C {-1:2, 0:1, 1:3}

D {0:1, 1:3, 2:7}

💡 Hint

Check the 'Top View Map' column at step 15 in the execution_table

At which step does the node with value 7 get added to the top view?

A Step 13

B Step 20

C Step 21

D Step 22

💡 Hint

Look for the step where 'Add node to top view' operation happens for node 7 in execution_table

If the node with value 5 had no children, how would the queue state change after step 16?

A Queue would be [(6,0),(7,2)]

B Queue would be [(6,0)]

C Queue would be [(7,2)]

D Queue would be empty

💡 Hint

Check the queue state after step 16 and consider no children enqueued for node 5

Concept Snapshot

Top View of Binary Tree:
- Traverse tree level by level (BFS)
- Track horizontal distance (hd) from root (0)
- For each hd, record first node encountered
- Left child hd = hd - 1, right child hd = hd + 1
- Print nodes in order of hd for top view

Full Transcript

The top view of a binary tree shows nodes visible when looking from above. We start at the root with horizontal distance zero. Using a queue, we traverse the tree level by level. For each node, we check if its horizontal distance is already recorded. If not, we add it to the top view map. We enqueue left and right children with updated horizontal distances. This process continues until all nodes are visited. The final top view is the nodes recorded at each horizontal distance, printed from leftmost to rightmost.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the top view concept

   The top view of a binary tree shows all nodes that are visible when looking down vertically from above the tree.

2. Step 2: Compare with other views

   Left, right, and bottom views show nodes visible from those sides, not from the top.

3. Final Answer:

   Nodes visible when the tree is viewed from the top -> Option A

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view shows nodes visible from above the tree [OK]

Common Mistakes:

• Confusing top view with left or right view
• Thinking bottom view is the same as top view

2. Which Rust data structure is best suited to store nodes with their horizontal distances for computing the top view of a binary tree?

easy

A. HashMap

B. Vec<Node>

C. LinkedList<Node>

D. BinaryHeap<Node>

Solution

1. Step 1: Identify the need for horizontal distance mapping

   Top view requires tracking nodes by their horizontal distance from the root, which can be negative or positive integers.

2. Step 2: Choose a data structure for key-value mapping

   A HashMap with key as horizontal distance (i32) and value as Node is ideal for quick lookups and updates.

3. Final Answer:

   HashMap -> Option A

4. Quick Check:

   Use HashMap for horizontal distance mapping [OK]

Hint: Use HashMap to map horizontal distance to nodes [OK]

Common Mistakes:

• Using Vec which doesn't map keys to values
• Using LinkedList which is inefficient for lookups
• Using BinaryHeap which is for priority queues

3. Given the following Rust code snippet for top view traversal, what will be printed?

struct Node {
    val: i32,
    left: Option,
    right: Option,
}

// Tree:
//       1
//      / \
//     2   3
//      \   \
//       4   5

fn main() {
    let root = Node {
        val: 1,
        left: Some(Box::new(Node {
            val: 2,
            left: None,
            right: Some(Box::new(Node { val: 4, left: None, right: None })),
        })),
        right: Some(Box::new(Node {
            val: 3,
            left: None,
            right: Some(Box::new(Node { val: 5, left: None, right: None })),
        })),
    };
    // Assume top_view function prints top view nodes in order from left to right
    top_view(&root);
}

medium

A. [2, 4, 1, 3, 5]

B. [2, 1, 3, 5]

C. [4, 2, 1, 3, 5]

D. [1, 2, 3]

Solution

1. Step 1: Assign horizontal distances to nodes

   Root (1) is at 0, left child (2) at -1, right child (3) at +1, node 4 at 0 (right child of 2), node 5 at +2 (right child of 3).

2. Step 2: Determine top view nodes by horizontal distance

   For each horizontal distance, the first node encountered from top is chosen: -1: 2, 0: 1, +1: 3, +2: 5. Node 4 at 0 is below 1, so ignored.

3. Final Answer:

   [2, 1, 3, 5] -> Option B

4. Quick Check:

   Top view nodes by horizontal distance = [2, 1, 3, 5] [OK]

Hint: Pick first node at each horizontal distance from top [OK]

Common Mistakes:

• Including nodes below first at same horizontal distance
• Ignoring horizontal distances for nodes
• Confusing order of output

4. The following Rust code attempts to compute the top view of a binary tree but has a bug. What is the error?

fn top_view(root: &Node) {
    let mut map = std::collections::HashMap::new();
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((root, 0));

    while let Some((node, hd)) = queue.pop_front() {
        // Insert node if horizontal distance not present
        map.entry(hd).or_insert(node.val);

        if let Some(left) = &node.left {
            queue.push_back((left, hd - 1));
        }
        if let Some(right) = &node.right {
            queue.push_back((right, hd + 1));
        }
    }

    for key in map.keys() {
        println!("{}", map[key]);
    }
}

medium

A. The code inserts duplicate nodes for same horizontal distance

B. The queue is not initialized properly

C. The map keys are not sorted before printing, so output order is random

D. The code does not handle empty tree (root is None)

Solution

1. Step 1: Analyze map insertion and printing

   The code inserts nodes correctly using or_insert to keep first node per horizontal distance.

2. Step 2: Check output order

   HashMap keys are unordered, so iterating with map.keys() prints nodes in random order, not left to right.

3. Final Answer:

   The map keys are not sorted before printing, so output order is random -> Option C

4. Quick Check:

   Sort keys before printing top view [OK]

Hint: Sort horizontal distances before printing top view [OK]

Common Mistakes:

• Assuming HashMap keys are ordered
• Ignoring empty tree case (not asked here)
• Thinking queue initialization is wrong

5. You want to find the top view of a binary tree but only have the tree nodes and no horizontal distance stored. Which approach correctly computes the top view in Rust? A) Use a recursive function passing horizontal distance and level, store first node per horizontal distance with smallest level. B) Use a stack to traverse nodes and store last node per horizontal distance. C) Traverse the tree in preorder and print nodes as you visit. D) Use a queue but ignore horizontal distances and print nodes in insertion order.

hard

A. Preorder traversal printing nodes directly

B. Use stack and store last node per horizontal distance

C. Use queue ignoring horizontal distances

D. Use recursion with horizontal distance and level to track top nodes

Solution

1. Step 1: Understand top view requires horizontal distance and level

   Top view needs to know horizontal distance and the vertical level to pick the topmost node at each horizontal distance.

2. Step 2: Choose approach that tracks horizontal distance and level

   Recursive traversal passing horizontal distance and level, storing first node per horizontal distance with smallest level, correctly computes top view.

3. Final Answer:

   Use recursion with horizontal distance and level to track top nodes -> Option D

4. Quick Check:

   Track horizontal distance and level recursively [OK]

Hint: Track horizontal distance and level to find top nodes [OK]

Common Mistakes:

• Ignoring horizontal distance in traversal
• Using stack without tracking levels
• Printing nodes in preorder without filtering