💡 Problem Formulation: Building a binary tree from given traversal outputs is a fundamental problem in computer science. The task is to construct the original binary tree when given either an inorder or postorder sequence of its nodes. For example, given the inorder traversal [9,3,15,20,7] and postorder traversal [9,15,7,20,3], the desired output is the reconstructed binary tree object.
Method 1: Recursive Approach with Inorder and Postorder Arrays
This method involves a recursive construction of the tree by choosing the last element of the postorder array as the root and recursively building the left and right subtrees. The inorder array determines the subtrees’ bounds.
Here’s an example:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(inorder, postorder):
if not inorder or not postorder:
return None
root_val = postorder.pop()
root = TreeNode(root_val)
inorder_index = inorder.index(root_val)
root.right = buildTree(inorder[inorder_index+1:], postorder)
root.left = buildTree(inorder[:inorder_index], postorder)
return root
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
tree = buildTree(inorder, postorder)
print(tree.val, tree.left.val, tree.right.val)Output:
3 9 20
This code snippet defines a TreeNode class and a function buildTree, which recursively constructs the binary tree using the list slicing based on the current root node’s index in the inorder array. This recursion continues until all nodes are placed into the tree correctly.
Method 2: Recursive Approach with Index Mapping
This method is a variant of the previous one, but it uses a hashmap to store indices of inorder elements to improve lookup time. This optimization is particularly useful for trees with many nodes.
Here’s an example:
def buildTree(inorder, postorder):
in_map = {val: idx for idx, val in enumerate(inorder)}
def build(start, end):
if start > end:
return None
root_val = postorder.pop()
root = TreeNode(root_val)
root.right = build(in_map[root_val] + 1, end)
root.left = build(start, in_map[root_val] - 1)
return root
return build(0, len(inorder) - 1)Output:
The structure will be the same as the output of Method 1.
This function utilizes a hashmap to keep track of the indices at which each value appears in the inorder sequence, eliminating the need to search through the inorder array each time. The build helper function then uses these indices to demarcate the subtrees’ boundaries for recursive tree construction.
Method 3: Iterative Approach
An iterative way to build the tree using a stack which simulates the recursion stack. It iterates over the postorder array backward and adds nodes to the tree according to their right or left child relationship determined by the inorder traversal.
Here’s an example:
def buildTree(inorder, postorder):
if not postorder:
return None
root = TreeNode(postorder[-1])
stack = [root]
inorder_index = len(inorder) - 1
for i in range(len(postorder)-2, -1, -1):
next_node = TreeNode(postorder[i])
cur_node = None
while stack and stack[-1].val == inorder[inorder_index]:
cur_node = stack.pop()
inorder_index -= 1
if cur_node:
cur_node.left = next_node
else:
stack[-1].right = next_node
stack.append(next_node)
return rootOutput:
The structure will be the same as the output of Method 1.
This approach creates a tree iteratively by simulating a parent-child link through a stack rather than recursive calls. It continues to push nodes into the stack if the top of the stack does not match the current node in inorder traversal, indicating that there is a left child to be processed. The process repeats for the right child.
Method 4: Optimized Recursive Approach with Pointers
An optimized recursive approach that avoids array slicing by maintaining pointers to array bounds instead of making copies, minimizing memory usage and potential overhead.
Here’s an example:
def buildTree(inorder, postorder):
def build(bound=None):
if not postorder or inorder[-1] == bound:
return None
root_val = postorder.pop()
root = TreeNode(root_val)
root.right = build(root_val)
inorder.pop()
root.left = build(bound)
return root
return build()Output:
The structure will be the same as the output of Method 1.
This approach makes use of a helper function that uses a boundary value to determine the end of the left or right subtree in the inorder traversal to avoid slicing arrays. The pop operations on both traversals align the tree nodes properly while the stack unwinds.
Bonus One-Liner Method 5: Using Generators
A Pythonic way that leverages the power of generators for an elegant and concise implementation to rebuild the tree.
Here’s an example:
def buildTree(inorder, postorder):
inorder_map = {val: idx for idx, val in enumerate(inorder)}
postorder_iter = reversed(postorder)
def build(end):
if inorder[-1] == end:
return None
root_val = next(postorder_iter)
root = TreeNode(root_val)
root.right = build(root_val)
inorder.pop()
root.left = build(end)
return root
return build(None)Output:
The structure will be the same as the output of Method 1.
This is a more condensed version of Method 4 that uses reversed postorder traversal and generators. The next call on the postorder iterator replaces the pop method, while the last seen value from inorder serves as a boundary condition.
Summary/Discussion
- Method 1: Recursive Approach with Inorder and Postorder Arrays. Strengths: Easy to understand. Weaknesses: Inefficient with large trees due to repeated slicing of arrays and searching for the root index in inorder.
- Method 2: Recursive Approach with Index Mapping. Strengths: Efficient with large trees due to the use of hashmap. Weaknesses: More memory usage compared to the first method due to the additional hashmap.
- Method 3: Iterative Approach. Strengths: Non-recursive, which can be advantageous for very deep trees where recursion could cause a stack overflow. Weaknesses: More complex logic and harder to debug.
- Method 4: Optimized Recursive Approach with Pointers. Strengths: Memory efficient. Weaknesses: Could be harder to conceptualize due to boundary handling.
- Method 5: Using Generators. Strengths: Clean and Pythonic. Weaknesses: The use of generators may make it difficult for beginners to understand flow control.