Top View of Binary Tree in DSA Rust

Mental Model

We want to see the nodes visible when looking at the tree from above, ignoring nodes hidden behind others.

Analogy: Imagine standing on a balcony looking down at a city street with tall buildings; you only see the rooftops that are not blocked by taller buildings in front.

       1
      / \
     2   3
      \   \
       4   5

Top view shows nodes: 2 -> 1 -> 3 -> 5

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 \ \ 4 5

Goal: Print nodes visible from top view: nodes that appear first at each horizontal distance from root

Step 1: Start BFS from root (1) at horizontal distance 0

Queue: [(1, hd=0)]
Top view map: {}

Why: We begin from root to explore nodes level by level with horizontal distances

Step 2: Dequeue (1, hd=0), record 1 at hd=0

Queue: []
Top view map: {0: 1}

Why: First node at hd=0 is 1, so it is visible from top

Step 3: Enqueue left child (2, hd=-1) and right child (3, hd=1)

Queue: [(2, hd=-1), (3, hd=1)]
Top view map: {0: 1}

Why: Children are added with updated horizontal distances

Step 4: Dequeue (2, hd=-1), record 2 at hd=-1

Queue: [(3, hd=1)]
Top view map: {-1: 2, 0: 1}

Why: First node at hd=-1 is 2, so it is visible from top

Step 5: Enqueue right child (4, hd=0) of node 2

Queue: [(3, hd=1), (4, hd=0)]
Top view map: {-1: 2, 0: 1}

Why: 4 is at hd=0 but 1 is already recorded at hd=0, so 4 won't overwrite

Step 6: Dequeue (3, hd=1), record 3 at hd=1

Queue: [(4, hd=0)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: First node at hd=1 is 3, so it is visible from top

Step 7: Enqueue right child (5, hd=2) of node 3

Queue: [(4, hd=0), (5, hd=2)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: Add node 5 with hd=2

Step 8: Dequeue (4, hd=0), hd=0 already recorded, skip recording

Queue: [(5, hd=2)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: 4 is hidden behind 1 at hd=0

Step 9: Dequeue (5, hd=2), record 5 at hd=2

Queue: []
Top view map: {-1: 2, 0: 1, 1: 3, 2: 5}

Why: First node at hd=2 is 5, so it is visible from top

Result:

Top view nodes in order of horizontal distance:
2 -> 1 -> 3 -> 5 -> null

Annotated Code

DSA Rust

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

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

impl Node {
    fn new(val: i32) -> Self {
        Node { val, left: None, right: None }
    }
}

fn top_view(root: &Option<Box<Node>>) {
    if root.is_none() {
        println!("null");
        return;
    }

    let mut queue: VecDeque<(&Box<Node>, i32)> = VecDeque::new();
    let mut top_map: BTreeMap<i32, i32> = BTreeMap::new();

    queue.push_back((root.as_ref().unwrap(), 0));

    while let Some((node, hd)) = queue.pop_front() {
        if !top_map.contains_key(&hd) {
            top_map.insert(hd, node.val); // record first node at this horizontal distance
        }

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

    // print top view nodes in order of horizontal distance
    for val in top_map.values() {
        print!("{} -> ", val);
    }
    println!("null");
}

fn main() {
    // Construct the tree:
    //        1
    //       / \
    //      2   3
    //       \   \
    //        4   5

    let mut root = Box::new(Node::new(1));
    let mut node2 = Box::new(Node::new(2));
    let mut node3 = Box::new(Node::new(3));
    let node4 = Box::new(Node::new(4));
    let node5 = Box::new(Node::new(5));

    node2.right = Some(node4);
    node3.right = Some(node5);
    root.left = Some(node2);
    root.right = Some(node3);

    top_view(&Some(root));
}

queue.push_back((root.as_ref().unwrap(), 0));

start BFS from root with horizontal distance 0

if !top_map.contains_key(&hd) { top_map.insert(hd, node.val); }

record first node encountered at each horizontal distance

queue.push_back((left, hd - 1));

enqueue left child with hd one less than current

queue.push_back((right, hd + 1));

enqueue right child with hd one more than current

for val in top_map.values() { print!("{} -> ", val); }

print nodes in order of horizontal distance for top view

Output

2 -> 1 -> 3 -> 5 -> null

Complexity Analysis

Time: O(n) because we visit each node once during BFS

Space: O(n) for queue and map storing nodes and horizontal distances

vs Alternative: Naive approach might try to track all nodes per horizontal distance and pick topmost, which is more complex; BFS with map is efficient and clean

Edge Cases

Empty tree

Prints 'null' as no nodes exist

DSA Rust

if root.is_none() { println!("null"); return; }

Single node tree

Prints the single node value followed by null

DSA Rust

queue.push_back((root.as_ref().unwrap(), 0));

Tree with multiple nodes at same horizontal distance

Only the first node encountered at that horizontal distance is recorded

DSA Rust

if !top_map.contains_key(&hd) { top_map.insert(hd, node.val); }

When to Use This Pattern

When asked to find nodes visible from top or bottom view of a binary tree, use BFS with horizontal distances to track first or last nodes at each horizontal distance.

Common Mistakes

Mistake: Overwriting nodes in map for the same horizontal distance instead of keeping the first one
Fix: Check if horizontal distance key exists before inserting to keep only the first node

Mistake: Using DFS which can miss correct order of nodes by level
Fix: Use BFS to process nodes level by level ensuring correct top view

Summary

Prints nodes visible from top when looking down on a binary tree.

Use when you need to see the first node at each horizontal distance from root.

The key is to track horizontal distances and record the first node encountered at each distance using BFS.

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