Reconstruct a Binary Tree from Preorder and Postorder Traversals

Question

The question asks the candidate to reconstruct a binary tree given its preorder and postorder traversal arrays.

Codemia · Accepted Answer

To reconstruct a binary tree from its preorder and postorder traversals, we can utilize the properties of these traversals. In preorder traversal, the first element is always the root of the tree. In postorder traversal, the last element is the root. By using these properties, we can recursively build the tree.

1. Start with the first element of the preorder array as the root.  
2. Find the index of this root in the postorder array.  
3. Elements to the left of this index in postorder belong to the left subtree, and elements to the right belong to the right subtree.  
4. Recursively apply the same logic to construct the left and right subtrees.

The time complexity of this algorithm is O(n) since we traverse each node once. The space complexity is O(n) as well, due to the recursion stack and the storage of the tree nodes.

```python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def constructFromPrePost(self, preorder, postorder):
        if not preorder or not postorder:
            return None
        root = TreeNode(preorder[0])
        if len(preorder) == 1:
            return root
        left_subtree_root_val = preorder[1]
        left_subtree_size = postorder.index(left_subtree_root_val) + 1
        root.left = self.constructFromPrePost(preorder[1:left_subtree_size + 1], postorder[:left_subtree_size])
        root.right = self.constructFromPrePost(preorder[left_subtree_size + 1:], postorder[left_subtree_size:-1])
        return root
```

Interviewers look for clarity in the candidate's explanation of the approach. They also assess the ability to write clean and efficient code, handle edge cases, and articulate the time and space complexity of the solution.

Reconstruct a Binary Tree from Preorder and Postorder Traversals

ByteDance

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

ByteDance Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string