💡 Problem Formulation: Given a binary tree, the task is to compute its top view. The top view is the set of nodes visible when the tree is viewed from the top. For example, given a binary tree, we want to return the node values that are visible from a top view alignment, from left to right.
Method 1: Horizontal Distance Mapping
This method involves assigning a horizontal distance value to each node. Nodes with the same horizontal distance are on the same vertical line. We use level-order traversal to determine which nodes appear in the top view, keeping track of the horizontal distances and the first occurrence at each distance.
Here’s an example:
from collections import deque
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
def top_view(root):
if root is None:
return []
q = deque()
top_view_map = {}
q.append((root, 0))
while q:
node, hd = q.popleft()
if hd not in top_view_map:
top_view_map[hd] = node.val
if node.left:
q.append((node.left, hd - 1))
if node.right:
q.append((node.right, hd + 1))
return [top_view_map[i] for i in sorted(top_view_map)]
# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.right = TreeNode(5)
root.left.right.right.right = TreeNode(6)
print(top_view(root))
Output:
[2, 1, 3, 6]
This snippet defines a binary tree and uses the function top_view to find and print the top view of the tree. The top_view function creates a dictionary that maps the horizontal distances to their first encountered node’s value, ensuring only top-view nodes are considered. The final result is sorted and returned based on horizontal distances.
Method 2: Recursive Pre-order Traversal
In this method, we traverse the tree using a pre-order recursion. We pass down the level and horizontal distance information as we go, storing the nodes’ values with their horizontal distance. For each horizontal distance, we keep the node that appears first (at the smallest level).
Here’s an example:
def find_top_view(root):
def recurse(node, dist, level, view):
if node is None:
return
if dist not in view or view[dist][1] > level:
view[dist] = (node.val, level)
recurse(node.left, dist - 1, level + 1, view)
recurse(node.right, dist + 1, level + 1, view)
top_view_map = {}
recurse(root, 0, 0, top_view_map)
return [top_view_map[i][0] for i in sorted(top_view_map)]
# Example usage:
# (Same Tree as Method 1)
print(find_top_view(root))
Output:
[2, 1, 3, 6]
The recursive pre-order traversal in find_top_view function accumulates the top-view by comparing levels at which nodes appear. It uses a helper function recurse with parameters for the node, its horizontal distance, level, and a dictionary that stores the current view. The final top view is again sorted according to the horizontal distances.
Method 3: Depth First Search (DFS) using a Stack
Similar to the recursive approach, this method uses a stack to perform an iterative depth-first search. Besides pushing node references onto the stack, the method also saves horizontal distance information and level, allowing us to filter nodes that should appear in the top view.
Here’s an example:
def top_view_dfs(root):
if not root:
return []
view, stack = {}, [(root, 0, 0)]
while stack:
node, dist, lvl = stack.pop()
if dist not in view or view[dist][1] > lvl:
view[dist] = (node.val, lvl)
if node.right:
stack.append((node.right, dist + 1, lvl + 1))
if node.left:
stack.append((node.left, dist - 1, lvl + 1))
return [view[d][0] for d in sorted(view)]
# Example usage:
# (Same Tree as Method 1)
print(top_view_dfs(root))
Output:
[2, 1, 3, 6]
The top_view_dfs function pushes a tuple, which includes the node alongside its horizontal distance and level, onto the stack. While popping items off the stack, the function maintains the top view in the dictionary view, ensuring only the relevant nodes are kept. The final output is sorted by the horizontal distance keys.
Method 4: Using a Sorted Dictionary
This approach simplifies the access and sorting of the horizontal distances using Python’s collections.OrderedDict or sortedcontainers.SortedDict. This method allows the dictionary to maintain its order, saving additional sorting steps in the end.
Here’s an example:
from collections import deque, OrderedDict
def top_view_sorted_dict(root):
if root is None:
return []
q = deque()
top_view_map = OrderedDict()
q.append((root, 0))
while q:
node, hd = q.popleft()
if hd not in top_view_map:
top_view_map[hd] = node.val
if node.left:
q.append((node.left, hd - 1))
if node.right:
q.append((node.right, hd + 1))
return list(top_view_map.values())
# Example usage:
# (Same Tree as Method 1)
print(top_view_sorted_dict(root))
Output:
[2, 1, 3, 6]
This method modifies the first approach to use an OrderedDict to simplify code and improve readability. The rest of the process mirrors Method 1, traversing the tree in a level-order manner and tracking the nodes in the top view based on their horizontal distances.
Bonus One-Liner Method 5: Comprehension with Default Dictionary
For those who love Python’s conciseness, this one-liner uses a default dictionary combined with a list comprehension to achieve the same result, assuming we have a utility function to provide nodes with their horizontal distances in a tuple.
Here’s an example:
from collections import defaultdict
def get_nodes_with_distance(root):
# This function would return a list of tuples (node value, horizontal distance)
# Implementation of this utility function is left as an exercise to the reader.
pass
# One-liner to find top view (assuming 'nodes_with_distance' is available):
top_view_oneliner = lambda nodes_with_distance: [min(
(node for node in nodes_with_distance if node[1] == d), key=lambda x: x[2])[0]
for d in set(node[1] for node in nodes_with_distance)]
# Example usage:
# (Same Tree as Method 1, after defining 'get_nodes_with_distance' utility function)
nodes_with_distance = get_nodes_with_distance(root)
print(top_view_oneliner(nodes_with_distance))
Output:
[2, 1, 3, 6]
This compact function top_view_oneliner leverages list comprehensions and a default dictionary to construct the top view of a binary tree. A helper function would be needed to iterate over the tree to gather nodes and their respective distances; the one-liner then filters and sorts these nodes to produce the top view.
Summary/Discussion
Method 1: Horizontal Distance Mapping. Offers a straightforward approach. Efficiency might be impacted when dealing with large trees due to sorting the keys.
Method 2: Recursive Pre-order Traversal. Elegant recursive solution. Could lead to stack overflow on highly unbalanced or deep trees.
Method 3: Depth First Search (DFS) using a Stack. Avoids the potential stack overflow of recursion. It is slightly more complex due to manual stack management.
Method 4: Using a Sorted Dictionary. Clean and efficient due to the internal ordering; it requires an additional ordered or sorted dictionary data structure.
Method 5: Comprehension with Default Dictionary. Very concise and Pythonic, but less readable and requires a pre-built list of nodes with distances.