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