Bottom View of a Binary Tree

Algorithm Steps

If the binary tree is empty, return an empty result.
Initialize a queue and enqueue the root node along with its horizontal distance (hd = 0).
Initialize an empty map (hdMap) to store the latest node value at each horizontal distance.
While the queue is not empty, dequeue an element (node, hd).
Update hdMap[hd] with the node's value (this ensures the bottom-most node at that hd is recorded).
If the node has a left child, enqueue it with hd - 1; if it has a right child, enqueue it with hd + 1.
After processing all nodes, sort the keys of hdMap and record their corresponding values. The ordered values form the bottom view of the binary tree.

Bottom View of a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque

def bottomView(root):
    if not root:
        return []
    q = deque([(root, 0)])
    hdMap = {}
    while q:
        node, hd = q.popleft()
        hdMap[hd] = node.val
        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))
    result = [hdMap[hd] for hd in sorted(hdMap)]
    return result

if __name__ == '__main__':
    # Construct binary tree:
    #         20
    #        /  \
    #       8    22
    #      / \     \
    #     5   3     25
    #        / \
    #       10  14
    root = TreeNode(20,
                    TreeNode(8, TreeNode(5), TreeNode(3, TreeNode(10), TreeNode(14))),
                    TreeNode(22, None, TreeNode(25)))
    print(bottomView(root))