💡 Problem Formulation: In binary tree processing, it is often required to find nodes at a specific depth. A particular challenge is to find the second deepest node, that is, the node one level above the deepest leaf nodes. Given a binary tree, for example:
a
/ \
b c
/ \ /
d e f
the second deepest nodes are b and c. The aim is to identify such nodes programmatically in Python.
Method 1: Depth-First Search (DFS) with Level Recording
This method involves traversing the tree using DFS and maintaining a record of each node’s level. When a leaf node is encountered it’s level – 1 is considered as a potential second deepest level.
Here’s an example:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.val = value
self.left = left
self.right = right
def find_second_deepest_node(root):
def dfs(node, depth):
nonlocal max_depth, second_deepest
if node:
if not node.left and not node.right: # leaf node
if depth > max_depth:
max_depth, second_deepest = depth, max_depth
else:
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
max_depth, second_deepest = -1, -1
dfs(root, 0)
return second_deepest
# Construct a test tree:
# a
# / \\
# b c
# /
# d
root = TreeNode('a', TreeNode('b', TreeNode('d')), TreeNode('c'))
print(find_second_deepest_node(root))
The output of this code snippet is:
1
This code creates a simple binary tree and defines a function to find the second deepest node’s depth by keeping track of the maximum depth and updating the second deepest level when a new max depth is found. Levels start at 0 for the root.
Method 2: Iterative Breadth-First Search (BFS)
The iterative BFS approach uses a queue to traverse the tree level by level, hence easily maintaining the depth count. The second deepest nodes can be tracked while proceeding through the levels.
Here’s an example:
from collections import deque
def find_second_deepest_node(root):
if not root: return None
queue = deque([(root, 0)])
depth_nodes = {}
while queue:
node, depth = queue.popleft()
depth_nodes.setdefault(depth, []).append(node.val)
if node.left: queue.append((node.left, depth+1))
if node.right: queue.append((node.right, depth+1))
second_deepest_level = sorted(depth_nodes.keys())[-2]
return depth_nodes[second_deepest_level]
print(find_second_deepest_node(root))
The output of this code snippet is:
['b', 'c']
This code snippet implements BFS to find the second deepest level nodes by maintaining a dictionary that records all nodes at each depth. The second deepest nodes can then be retrieved from this dictionary.
Method 3: Two-Pass DFS
In the two-pass DFS approach, we first find the maximum depth, then perform another DFS to find nodes that are one level shallower than the maximum depth. This ensures that we identify the second deepest nodes.
Here’s an example:
def max_depth(root): if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right)) def find_second_deepest_nodes(root, depth=0): if not root: return [] if depth == desired_second_deepest_level: return [root.val] return find_second_deepest_nodes(root.left, depth+1) + find_second_deepest_nodes(root.right, depth+1) desired_second_deepest_level = max_depth(root) - 1 print(find_second_deepest_nodes(root))
The output of this code snippet is:
['b', 'c']
This method first computes the maximum depth and then traverses the tree again to find all nodes at the second deepest level, which is one less than the maximum depth.
Method 4: Modified Level Order Traversal
A slight variation of the level-order traversal BFS can be modified to keep track only of nodes at the last two levels. When traversal is complete, the second last list of nodes reveals the second deepest nodes.
Here’s an example:
def find_second_deepest_node(root):
if not root: return None
queue = deque([root])
last, second_last = [], []
while queue:
second_last = last
last = [node for node in queue]
length = len(queue)
for i in range(length):
node = queue.popleft()
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return [node.val for node in second_last]
print(find_second_deepest_node(root))
The output of this code snippet is:
['b', 'c']
The code performs a modified BFS and updates the last and second-last level node lists at each level. By the end of the traversal, the second-last list holds the second deepest nodes.
Bonus One-Liner Method 5: Functional Approach Using Recursion
The functional one-liner uses recursive expressions coupled with Python’s powerful list comprehension and conditional expression. It elegantly combines steps of the previous DFS methods in succinct logic.
Here’s an example:
find_second_deepest = lambda r, d=0, md=[-1]: [r.val] if d == md[0] else (md.append(d) or []) if not r.left and not r.right and md[0] < d else (find_second_deepest(r.left, d+1, md) + find_second_deepest(r.right, d+1, md)) print(find_second_deepest(root))
The output of this code snippet is:
['b', 'c']
This one-liner defines a lambda function that traverses the tree and uses a mutable default argument to keep track of the maximum depth, returning nodes at the second deepest level.
Summary/Discussion
- Method 1: DFS with Level Recording. Straightforward. Suits trees with distinct levels. Costs extra space proportional to tree height.
- Method 2: Iterative BFS. Level order is explicit. Easy to understand. Extra space for queue and node depth tracking.
- Method 3: Two-Pass DFS. Explicit depth computation. Simple. Requires two traversals of the tree.
- Method 4: Modified Level Order Traversal. Efficient use of space. Only stores last two levels. Code can be less intuitive than standard BFS.
- Method 5: Functional One-Liner. Concise, but can be difficult to read or understand. Relies on Python-specific features.