💡 Problem Formulation: In binary tree data structures, each node may have up to two children. This article addresses the task of traversing a binary tree with Python to print the values of the nodes located in the left subtree. For example, given a binary tree with the root node value 10, left child node value 8, and right child having the value 12, the desired output would be to print only the value ‘8’ from the left subtree.
Method 1: Recursive Pre-order Traversal
This method involves a recursive function that traverses the tree in pre-order (root-left-right) but only prints nodes when traversing the left child. It’s a direct approach and respects the recursive nature of trees.
Here’s an example:
class TreeNode:
def __init__(self, value):
self.left = None
self.right = None
self.val = value
def print_left_subtree(root):
if root is not None:
if root.left:
print(root.left.val)
print_left_subtree(root.left)
if root.right:
print_left_subtree(root.right)
# Example usage:
root = TreeNode(10)
root.left = TreeNode(8)
root.right = TreeNode(12)
print_left_subtree(root)The output of this code snippet will be:
8
This snippet defines a binary tree and a function print_left_subtree() that recursively traverses the tree. When the function encounters a left child, it prints its value before recursively calling itself with the left child as the new root, ensuring only nodes in the left subtree are printed.
Method 2: Iterative Depth-First Search (DFS)
Iterative DFS uses a stack to traverse the tree, pushing left children onto the stack. This simulates the recursive stack but avoids the potential for stack overflow on very deep trees, which can occur with recursive methods.
Here’s an example:
from collections import deque
class TreeNode:
# ... TreeNode definition as above ...
def print_left_subtree_iterative(root):
if not root:
return
stack = deque([root])
while stack:
current = stack.pop()
if current.right:
stack.append(current.right)
if current.left:
print(current.left.val)
stack.append(current.left)
# Example usage:
root = TreeNode(10)
# ... Build tree as above ...
print_left_subtree_iterative(root)The output of this code example will be:
8
The function print_left_subtree_iterative() uses a stack to iterate through the tree nodes. When a left child is encountered, it prints its value before pushing it onto the stack, ensuring that only nodes from the left subtree are printed.
Method 3: Level-order Traversal (Breadth-First Search)
Breadth-First Search (BFS) uses a queue to traverse the tree level by level, only printing nodes from the left subtree at each level. This guarantees that all nodes are visited and processed in level order.
Here’s an example:
from collections import deque
class TreeNode:
# ... TreeNode definition as above ...
def print_left_subtree_bfs(root):
if not root:
return
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
current = queue.popleft()
if i == 0 and current.left:
print(current.left.val)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
# Example usage:
root = TreeNode(10)
# ... Build tree as above ...
print_left_subtree_bfs(root)The output of this code example will be:
8
Here, print_left_subtree_bfs() performs a level-order traversal, but only prints the leftmost node of each level (except the root), guaranteeing that it will print only nodes in the left subtree.
Bonus One-Liner Method 5: Functional Approach with Filter and Map
Combining Python’s filter() and map() offers a one-liner functional alternative for traversing and printing the left subtree if an appropriate tree traversal list is provided.
Here’s an example:
# Assuming 'inorder_traversal' is a list of nodes in inorder. # TreeNode definition as above. print(*map(lambda x: x.val, filter(lambda x: x.is_left, inorder_traversal)), sep="\n")
The expected output:
8
This line filters inorder_traversal to include only nodes flagged as ‘is_left’, then maps the node values and prints them. This method relies on the tree traversal list to have already been generated, with nodes correctly flagged.
Summary/Discussion
- Method 1: Recursive Pre-order Traversal. Direct and natural for tree structures. Risk of stack overflow for deep trees.
- Method 2: Iterative DFS with Stack. Iterative alternative for deep trees. Requires manual stack management.
- Method 3: Level-order Traversal (BFS). Processes nodes level by level. Can be less intuitive and requires queue management.
- Bonus Method 5: Functional with Filter and Map. Concise and elegant. Assumes pre-existent traversal list with flags.