Binary tree bottom view

Binary tree bottom view

December 14, 2023
medium
graph, BFS

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 and right).

Function: bottomView(root) #

This function calculates the bottom view of the binary tree.

  1. Base Case Check:

    • If the root is None (i.e., the tree is empty), the function returns an empty list.

  2. 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 - Breadth-First Search). Each element is a tuple containing a node, its horizontal distance, and depth.

  3. 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.

  4. 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.

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.