Reconstructing Binary Trees from Traversals

Introduction

Binary trees are fundamental data structures in computer science, and understanding how to work with them is crucial for many programming tasks. One interesting problem is reconstructing a binary tree from its traversals. In this article, we'll explore how to reconstruct binary trees using combinations of inorder, preorder, and postorder traversals.

Traversal Types

Before we dive into reconstruction, let's quickly review the three main types of tree traversals:

1. Inorder: Left subtree, Root, Right subtree
2. Preorder: Root, Left subtree, Right subtree
3. Postorder: Left subtree, Right subtree, Root

Reconstructing from Inorder and Preorder Traversals

Let's start with reconstructing a binary tree from its inorder and preorder traversals. Here's the algorithm:

1. The first element in the preorder traversal is always the root of the tree.
2. Find the root element in the inorder traversal. Elements to its left form the left subtree, and elements to its right form the right subtree.
3. Recursively apply this process to construct left and right subtrees.

Here's a Java implementation:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    private int preIndex = 0;
    private Map<Integer, Integer> inorderMap = new HashMap<>();
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, 0, inorder.length - 1);
    }
    
    private TreeNode buildTreeHelper(int[] preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        
        TreeNode root = new TreeNode(preorder[preIndex++]);
        int inIndex = inorderMap.get(root.val);
        
        root.left = buildTreeHelper(preorder, inStart, inIndex - 1);
        root.right = buildTreeHelper(preorder, inIndex + 1, inEnd);
        
        return root;
    }
}

Let's walk through an example:

Inorder:   [4, 2, 5, 1, 6, 3, 7]
Preorder:  [1, 2, 4, 5, 3, 6, 7]

1. The root is 1 (first element in preorder).
2. In the inorder traversal, elements left of 1 (4, 2, 5) form the left subtree, and elements right of 1 (6, 3, 7) form the right subtree.
3. We recursively apply this process to build the entire tree.

Reconstructing from Inorder and Postorder Traversals

Now, let's look at reconstructing a binary tree from its inorder and postorder traversals. The process is similar, but with a key difference:

1. The last element in the postorder traversal is always the root of the tree.
2. Find the root element in the inorder traversal. Elements to its left form the left subtree, and elements to its right form the right subtree.
3. Recursively apply this process to construct right and left subtrees (note the order change).

Here's a Java implementation:

class Solution {
    private int postIndex;
    private Map<Integer, Integer> inorderMap = new HashMap<>();
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(postorder, 0, inorder.length - 1);
    }
    
    private TreeNode buildTreeHelper(int[] postorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        
        TreeNode root = new TreeNode(postorder[postIndex--]);
        int inIndex = inorderMap.get(root.val);
        
        root.right = buildTreeHelper(postorder, inIndex + 1, inEnd);
        root.left = buildTreeHelper(postorder, inStart, inIndex - 1);
        
        return root;
    }
}

Let's walk through an example:

Inorder:    [4, 2, 5, 1, 6, 3, 7]
Postorder:  [4, 5, 2, 6, 7, 3, 1]

1. The root is 1 (last element in postorder).
2. In the inorder traversal, elements left of 1 (4, 2, 5) form the left subtree, and elements right of 1 (6, 3, 7) form the right subtree.
3. We recursively apply this process to build the entire tree, starting with the right subtree.

Time and Space Complexity

For both reconstruction methods:

• Time Complexity: O(n), where n is the number of nodes in the tree.
• Space Complexity: O(n) for the hash map and the recursion stack.

Conclusion

Reconstructing binary trees from their traversals is a fascinating problem that combines your understanding of tree structures and recursive thinking. By mastering these techniques, you'll be well-equipped to handle a variety of tree-related problems in your coding interviews and real-world applications.

Remember, practice is key to becoming proficient with these algorithms. Try implementing these solutions and test them with various input combinations to solidify your understanding.