**π‘ Problem Formulation:** In this article, we’ll explore how to determine if two binary trees have the same leaf traversal sequence using Python. Given two binary tree root nodes, the goal is to verify if the sequence of leaves visited in a left-to-right order is identical for both trees. For instance, if both trees’ leaves result in the sequence [1, 2, 3], then they have the same leaf traversal.

## Method 1: Recursive Pre-order Traversal

This method uses a recursive pre-order traversal to collect the leaves of both trees into lists. Once the leaves are collected, they can be compared for equality. It’s a simple and straightforward approach that utilizes recursion to navigate the trees.

Here’s an example:

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def getLeaves(root, leaves): if root: getLeaves(root.left, leaves) if not root.left and not root.right: leaves.append(root.val) getLeaves(root.right, leaves) def sameLeafTraversal(root1, root2): leaves1 = [] leaves2 = [] getLeaves(root1, leaves1) getLeaves(root2, leaves2) return leaves1 == leaves2 # Example Trees tree1 = TreeNode(1) tree1.left = TreeNode(2) tree1.right = TreeNode(3) tree2 = TreeNode(1) tree2.left = TreeNode(3) tree2.right = TreeNode(2) print(sameLeafTraversal(tree1, tree2))

Output: `True`

or `False`

depending on the leaf traversal sequence.

This code defines a `TreeNode`

class and a function `getLeaves`

that collects all the leaf nodes’ values from a binary tree into a list passed by reference. The main function, `sameLeafTraversal`

, uses this helper function to capture the leaves of both trees and then compares the lists to check if they are equal.

## Method 2: Iterative Pre-order Traversal with Stack

The iterative pre-order traversal replicates the recursion stack using an explicit `stack`

data structure. This method can sometimes be more efficient since it avoids the overhead of recursive function calls.

Here’s an example:

def getLeavesIteratively(root): stack, leaves = [root], [] while stack: node = stack.pop() if node: if not node.left and not node.right: leaves.append(node.val) stack.extend([node.right, node.left]) return leaves def sameLeafTraversalIterative(root1, root2): return getLeavesIteratively(root1) == getLeavesIteratively(root2) # Example Trees (same as above) print(sameLeafTraversalIterative(tree1, tree2))

Output: `True`

or `False`

depending on the leaf traversal sequence.

The function `getLeavesIteratively`

uses a stack to manage the nodes during traversal. Leaves are added to the `leaves`

list when a node without children is popped. The main function, `sameLeafTraversalIterative`

, calls this helper function for both trees and compares the results.

## Method 3: Space-Optimized Comparison

This method involves a simultaneous traversal of both trees, comparing leaf nodes on-the-fly. This can be more space-efficient as it avoids storing all leaf nodes.

Here’s an example:

def isSameLeafTraversal(root1, root2): stack1, stack2 = [root1], [root2] while stack1 and stack2: leaf1 = leaf2 = None while stack1: node1 = stack1.pop() if node1: stack1.extend([node1.right, node1.left]) if not node1.left and not node1.right: leaf1 = node1.val break while stack2: node2 = stack2.pop() if node2: stack2.extend([node2.right, node2.left]) if not node2.left and not node2.right: leaf2 = node2.val break if leaf1 != leaf2: return False return not stack1 and not stack2 # Example Trees (same as above) print(isSameLeafTraversal(tree1, tree2))

Output: `True`

or `False`

depending on the leaf traversal sequence.

This method uses two stacks to simultaneously traverse both trees. When a leaf node is reached in both trees, the values are compared immediately. The traversal stops if a mismatch is found or continues until all leaves have been visited.

## Method 4: Generator-Based Traversal

Utilizing Python’s generator functions, this method creates a generator for leaf node traversal in both trees and compares them in a single pass. It’s a memory-efficient approach as it does not store all leaves but yields them one at a time.

Here’s an example:

def leafGenerator(root): stack = [root] while stack: node = stack.pop() if node: if not node.left and not node.right: yield node.val stack.extend([node.right, node.left]) def sameLeafTraversalGenerator(root1, root2): return all(leaf1 == leaf2 for leaf1, leaf2 in zip(leafGenerator(root1), leafGenerator(root2))) # Example Trees (same as above) print(sameLeafTraversalGenerator(tree1, tree2))

Output: `True`

or `False`

depending on the leaf traversal sequence.

The `leafGenerator`

function is a generator that yields the value of each leaf node in a pre-order traversal. The main function `sameLeafTraversalGenerator`

uses Python’s `zip`

function to create pairs of leaf values from both trees and compares them.

## Bonus One-Liner Method 5: Using itertools and All

By combining the generator traversal with `itertools`

, this one-liner method uses the `all`

function to check for leaf node value equality in an efficient and succinct manner.

Here’s an example:

from itertools import zip_longest def sameLeafTraversalOneLiner(root1, root2): return all(l1 == l2 for l1, l2 in zip_longest(leafGenerator(root1), leafGenerator(root2), fillvalue=object())) # Example Trees (same as above) print(sameLeafTraversalOneLiner(tree1, tree2))

Output: `True`

or `False`

depending on the leaf traversal sequence.

This laconic version expands on the previous method by using `zip_longest`

from the `itertools`

module to handle trees with different numbers of leaves more gracefully, ensuring that an exhaustive comparison is made.

## Summary/Discussion

**Method 1:**Recursive Pre-order Traversal. Simple to understand and implement. Potentially uses more memory for large trees.**Method 2:**Iterative Pre-order Traversal. Avoids recursion overhead. Still requires memory to store all leaves.**Method 3:**Space-Optimized Comparison. More space-efficient, comparing leaves as they are found without storage. Requires careful management of traversal state.**Method 4:**Generator-Based Traversal. Memory-efficient and elegant, utilizing Python’s lazy evaluation. But less intuitive for those unfamiliar with generators.**Method 5:**One-Liner with itertools and All. Extremely concise and combines the strengths of the generator approach with robust handling via`zip_longest`

.

Emily Rosemary Collins is a tech enthusiast with a strong background in computer science, always staying up-to-date with the latest trends and innovations. Apart from her love for technology, Emily enjoys exploring the great outdoors, participating in local community events, and dedicating her free time to painting and photography. Her interests and passion for personal growth make her an engaging conversationalist and a reliable source of knowledge in the ever-evolving world of technology.