Binary tree bottom view
December 14, 2023
Problem #
The horizontal distance of a binary tree node describes how far left or right the node will be when the tree is printed out.
More rigorously, we can define it as follows:
The horizontal distance of the root is 0. The horizontal distance of a left child is hd(parent)  1. The horizontal distance of a right child is hd(parent) + 1. For example, for the following tree, hd(1) = 2, and hd(6) = 0.
5
/ \
3 7
/ \ / \
1 4 6 9
/ / 0 8 The bottom view of a tree, then, consists of the lowest node at each horizontal distance. If there are two nodes at the same depth and horizontal distance, either is acceptable.
For this tree, for example, the bottom view could be [0, 1, 3, 6, 8, 9].
Given the root to a binary tree, return its bottom view.
solution #
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def bottomView(root):
if not root:
return []
# Initialize a dictionary to store horizontal distance as key and (node value, depth) as value
hd_node = {}
# Queue for level order traversal. Each element is a tuple (node, horizontal distance, depth)
queue = [(root, 0, 0)]
while queue:
node, hd, depth = queue.pop(0)
# Update the dictionary with the node at the greatest depth for each horizontal distance
if hd not in hd_node or depth >= hd_node[hd][1]:
hd_node[hd] = (node.val, depth)
# Add left and right children to the queue
if node.left:
queue.append((node.left, hd  1, depth + 1))
if node.right:
queue.append((node.right, hd + 1, depth + 1))
# Extract the bottom view values from the dictionary, sorted by horizontal distance
bottom_view = [hd_node[hd][0] for hd in sorted(hd_node)]
return bottom_view
# Construct the binary tree from the problem statement
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root.left.left.left = TreeNode(0)
root.right.right.left = TreeNode(8)
# Get the bottom view of the binary tree
bottom_view = bottomView(root)
print(bottom_view)
Class Definition: TreeNode
#
TreeNode
is a class representing a node in a binary tree. Each
TreeNode
object has a value (val
), and pointers to its left and right child nodes (left
andright
).
Function: bottomView(root)
#
This function calculates the bottom view of the binary tree.

Base Case Check:
 If the
root
isNone
(i.e., the tree is empty), the function returns an empty list.
 If the

Initialization:
hd_node
: A dictionary to store information about nodes. The key is the “horizontal distance” (hd) from the root, and the value is a tuple(node value, depth)
.queue
: A list used for level order traversal (BFS  BreadthFirst Search). Each element is a tuple containing a node, its horizontal distance, and depth.

Level Order Traversal:
 The tree is traversed level by level.
 For each node encountered, it checks and updates
hd_node
with the node at the greatest depth for each horizontal distance.  It then adds the left and right children of the current node to the queue, adjusting their horizontal distance and depth accordingly.

Calculating Bottom View:
 The bottom view of the tree is extracted from
hd_node
. It consists of nodes that appear at the bottom at each horizontal distance when the tree is visualized.  The values are retrieved from
hd_node
, sorted by their horizontal distance keys.
 The bottom view of the tree is extracted from
Constructing and Testing the Tree #
 The code then constructs the specific binary tree provided in the problem statement.
 It creates a
TreeNode
for each node and links them as described (left and right children).  Finally, it calls
bottomView(root)
with the root of this tree and prints the result.
Output #
 The output is the bottom view of the given binary tree. It represents the nodes visible when the tree is viewed from the bottom, with each node’s position determined by its horizontal distance from the root.