Bottom view of BT

Intuition

To determine the bottom view of a binary tree, we need to capture the nodes that are visible when observing the tree from below. This involves identifying nodes that appear at the lowest vertical level for each horizontal distance from the root. A Breadth-First Search (BFS) traversal is well-suited for this task, as it processes nodes level by level. By tracking the horizontal distance of each node from the root and storing the most recent node encountered at each distance in a map, we can accurately capture the bottom view. The horizontal distance helps in maintaining the vertical alignment of nodes, ensuring that we only keep the nodes that are visible from the bottom.

Approach

Begin by initializing an empty vector to hold the final result of the bottom view.
If the tree is empty (i.e., the root is null), immediately return the empty result vector.
Create a map to store nodes based on their horizontal distances from the root. The map's key will be the horizontal distance, and the value will be the node's data, ensuring that only the latest node for each distance is recorded.
Set up a queue to facilitate BFS traversal. Each entry in the queue will be a pair consisting of a node and its corresponding horizontal distance.
Start the BFS traversal by enqueuing the root node with a horizontal distance of 0.
While the queue contains elements, execute the following steps:
- Dequeue the front element to retrieve the node and its associated horizontal distance.
- Update the map with the node's value for the current horizontal distance, ensuring that only the most recent node at each distance is stored.
- If the node has a left child, enqueue this child with a horizontal distance one less than the current node's distance.
- If the node has a right child, enqueue this child with a horizontal distance one more than the current node's distance.
After completing the BFS traversal, extract the values from the map in ascending order of their horizontal distances and store them in the result vector.
Return the result vector, which now contains the bottom view of the binary tree.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
  public:
    vector<int> bottomView(TreeNode *root) {
        // Vector to store the result
        vector<int> ans;
        
        // Check if the tree is empty
        if (root == nullptr) {
            return ans;
        }
        
        // Map to store the bottom view nodes
        // based on their vertical positions
        map<int, int> mpp;
        
        // Queue for BFS traversal, each
        // element is a pair containing node
        // and its vertical position
        queue<pair<TreeNode*, int>> q;
        
        // Push the root node with its vertical
        // position (0) into the queue
        q.push({root, 0});
        
        // BFS traversal
        while (!q.empty()) {
            // Retrieve the node and its vertical
            // position from the front of the queue
            auto it = q.front();
            q.pop();
            TreeNode* node = it.first;
            int line = it.second;
            
            // Update the map with the node's data
            // for the current vertical position
            mpp[line] = node->data;
            
            // Process left child
            if (node->left != nullptr) {
                // Push the left child with a decreased
                // vertical position into the queue
                q.push({node->left, line - 1});
            }
            
            // Process right child
            if (node->right != nullptr) {
                // Push the right child with an increased
                // vertical position into the queue
                q.push({node->right, line + 1});
            }
        }
        
        // Transfer values from the
        // map to the result vector
        for (auto it : mpp) {
            ans.push_back(it.second);
        }
        
        return ans;
    }
};

int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(10);
    root->left->left->right = new TreeNode(5);
    root->left->left->right->right = new TreeNode(6);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(10);
    root->right->left = new TreeNode(9);

    Solution solution;

    // Get the Bottom View traversal
    vector<int> bottomView = solution.bottomView(root);

    // Print the result
    cout << "Bottom View Traversal: " << endl;
    for (auto node : bottomView) {
        cout << node << " ";
    }

    return 0;
}
import java.util.*;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class Solution {
    public List<Integer> bottomView(TreeNode root) {
        // List to store the result
        List<Integer> ans = new ArrayList<>();

        // Check if the tree is empty
        if (root == null) {
            return ans;
        }

        // Map to store the bottom view nodes
        // based on their vertical positions
        Map<Integer, Integer> mpp = new TreeMap<>();

        // Queue for BFS traversal, each
        // element is a pair containing node
        // and its vertical position
        Queue<Map.Entry<TreeNode, Integer>> q = new LinkedList<>();

        // Push the root node with its vertical
        // position (0) into the queue
        q.add(new AbstractMap.SimpleEntry<>(root, 0));

        // BFS traversal
        while (!q.isEmpty()) {
            // Retrieve the node and its vertical
            // position from the front of the queue
            Map.Entry<TreeNode, Integer> it = q.poll();
            TreeNode node = it.getKey();
            int line = it.getValue();

            // Update the map with the node's data
            // for the current vertical position
            mpp.put(line, node.data);

            // Process left child
            if (node.left != null) {
                // Push the left child with a decreased
                // vertical position into the queue
                q.add(new AbstractMap.SimpleEntry<>(node.left, line - 1));
            }

            // Process right child
            if (node.right != null) {
                // Push the right child with an increased
                // vertical position into the queue
                q.add(new AbstractMap.SimpleEntry<>(node.right, line + 1));
            }
        }

        // Transfer values from the
        // map to the result list
        for (Map.Entry<Integer, Integer> it : mpp.entrySet()) {
            ans.add(it.getValue());
        }

        return ans;
    }

    public static void main(String[] args) {
        // Creating a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(10);
        root.left.left.right = new TreeNode(5);
        root.left.left.right.right = new TreeNode(6);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(10);
        root.right.left = new TreeNode(9);

        Solution solution = new Solution();

        // Get the Bottom View traversal
        List<Integer> bottomView = solution.bottomView(root);

        // Print the result
        System.out.println("Bottom View Traversal: ");
        for (int node : bottomView) {
            System.out.print(node + " ");
        }
    }
}
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def bottomView(self, root):
        # List to store the result
        ans = []

        # Check if the tree is empty
        if not root:
            return ans

        # Dictionary to store the bottom view nodes
        # based on their vertical positions
        mpp = {}

        # Queue for BFS traversal, each
        # element is a pair containing node
        # and its vertical position
        q = deque([(root, 0)])

        # BFS traversal
        while q:
            # Retrieve the node and its vertical
            # position from the front of the queue
            node, line = q.popleft()

            # Update the dictionary with the node's data
            # for the current vertical position
            mpp[line] = node.data

            # Process left child
            if node.left:
                # Push the left child with a decreased
                # vertical position into the queue
                q.append((node.left, line - 1))

            # Process right child
            if node.right:
                # Push the right child with an increased
                # vertical position into the queue
                q.append((node.right, line + 1))

        # Transfer values from the
        # dictionary to the result list
        for key in sorted(mpp.keys()):
            ans.append(mpp[key])

        return ans

if __name__ == "__main__":
    # Creating a sample binary tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(10)
    root.left.left.right = TreeNode(5)
    root.left.left.right.right = TreeNode(6)
    root.right = TreeNode(3)
    root.right.right = TreeNode(10)
    root.right.left = TreeNode(9)

    solution = Solution()

    # Get the Bottom View traversal
    bottom_view = solution.bottomView(root)

    # Print the result
    print("Bottom View Traversal: ")
    for node in bottom_view:
        print(node, end=" ")
// Definition for a binary tree node.
 class TreeNode {
       constructor(val = 0, left = null, right = null){
           this.data = val;
           this.left = left;
           this.right = right;
 }
  }
 
class Solution {
    bottomView(root) {
        // Array to store the result
        let ans = [];

        // Check if the tree is empty
        if (root === null) {
            return ans;
        }

        // Map to store the bottom view nodes
        // based on their vertical positions
        let mpp = new Map();

        // Queue for BFS traversal, each
        // element is a pair containing node
        // and its vertical position
        let q = [];
        q.push([root, 0]);

        // BFS traversal
        while (q.length > 0) {
            // Retrieve the node and its vertical
            // position from the front of the queue
            let [node, line] = q.shift();

            // Update the map with the node's data
            // for the current vertical position
            mpp.set(line, node.data);

            // Process left child
            if (node.left !== null) {
                // Push the left child with a decreased
                // vertical position into the queue
                q.push([node.left, line - 1]);
            }

            // Process right child
            if (node.right !== null) {
                // Push the right child with an increased
                // vertical position into the queue
                q.push([node.right, line + 1]);
            }
        }

        // Transfer values from the
        // map to the result array
        let keys = Array.from(mpp.keys()).sort((a, b) => a - b);
        for (let key of keys) {
            ans.push(mpp.get(key));
        }

        return ans;
    }
}

// Helper function to create a new TreeNode
function createTreeNode(val) {
    return new TreeNode(val);
}

// Main function to test the solution
function main() {
    // Creating a sample binary tree
    let root = createTreeNode(1);
    root.left = createTreeNode(2);
    root.left.left = createTreeNode(4);
    root.left.right = createTreeNode(10);
    root.left.left.right = createTreeNode(5);
    root.left.left.right.right = createTreeNode(6);
    root.right = createTreeNode(3);
    root.right.right = createTreeNode(10);
    root.right.left = createTreeNode(9);

    let solution = new Solution();

    // Get the Bottom View traversal
    let bottomView = solution.bottomView(root);

    // Print the result
    console.log("Bottom View Traversal: ");
    for (let node of bottomView) {
        console.log(node + " ");
    }
}

main();

Complexity Analysis

Time Complexity O(N), where N is the number of nodes in the binary tree. This arises from visiting each node exactly once during the BFS traversal.

Space Complexity O(N/2 + N/2), where N represents the number of nodes in the binary tree. The main space-consuming data structure is the queue used for BFS traversal. In the worst case of a balanced binary tree, the queue will have at most N/2 nodes, representing the maximum width of the tree.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts