Problem

Given the sequence of keys visited by a postorder traversal of a binary search tree, reconstruct the tree.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: postorder = [2, 4, 3, 8, 7, 5]
Output:
     5
    / \
   3   7
  / \   \
 2   4   8
Explanation: Given the sequence of postorder traversal [2, 4, 3, 8, 7, 5], the tree is constructed as shown above.

Solution

Method 1 - Using Recursion

Intuition

  • In a postorder traversal, the last element is always the root of the tree.
  • All elements to the left of this root in the traversal list are elements of the left subtree, and all elements to the right are elements of the right subtree.
  • Recursively apply the same logic to construct the left and right subtrees.

Approach

  1. Base Case: If the sequence is empty, return None.
  2. Root Identification: The last element of the sequence is the root of the subtree.
  3. Partition: Find the first index in the sequence from left where the elements are greater than the root. Elements before this index form the left subtree, and elements from this index to the end (excluding the last element) form the right subtree.
  4. Recursive Construction: Recursively construct the left and right subtrees using the identified partitions.
  5. Return Root: Create the root node with its left and right children.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public TreeNode buildTree(int[] postorder) {
        return helper(postorder, 0, postorder.length - 1);
    }

    private TreeNode helper(int[] postorder, int left, int right) {
        if (left > right) return null;

        // The last element of the postorder array will be the root.
        TreeNode root = new TreeNode(postorder[right]);
        int i;
        
        // Find the first element greater than the root to be the start of the right subtree
        for (i = left; i < right; i++) {
            if (postorder[i] > postorder[right]) break;
        }

        // Recursive reconstruction of left and right subtrees
        root.left = helper(postorder, left, i - 1);
        root.right = helper(postorder, i, right - 1);

        return root;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] postorder = {2, 4, 3, 8, 7, 5};
        TreeNode root = solution.buildTree(postorder);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:

    def buildTree(self, postorder: List[int]) -> Optional['Solution.TreeNode']:
        def helper(left: int, right: int) -> Optional['Solution.TreeNode']:
            if left > right:
                return None

            # The last element in the postorder segment is the root
            root_val = postorder[right]
            root = Solution.TreeNode(root_val)

            # Find the first element greater than root to separate left and right subtrees
            split_index = left
            while split_index < right and postorder[split_index] <= root_val:
                split_index += 1

            # Recursively build the left and right subtrees
            root.left = helper(left, split_index - 1)
            root.right = helper(split_index, right - 1)
            return root

        return helper(0, len(postorder) - 1)


# Example usage
sol = Solution()
postorder = [2, 4, 3, 8, 7, 5]
root = sol.buildTree(postorder)

Complexity

  • ⏰ Time complexity: O(n^2) in the worst case due to partitioning each subtree (resulting in significant amount of slicing).
  • 🧺 Space complexity: O(n) for the function call stack in the worst case for a highly unbalanced tree.