Reconstructing a Binary Tree from Traversal Sequences

Preorder, inorder, and postorder traversals of a binary tree are fundamental operations in data structures. Using these traversal sequences, the original binary tree can be uniquely reconstructed. This article provides a detailed explanation of how to reconstruct a binary tree from preorder and inorder traversals, as well as from postorder and inorder traversals, along with corresponding C code implementations.

Basic Concepts

Before we begin, we need to understand the three traversal methods:

1. Preorder Traversal: Order: Root node -> Left subtree -> Right subtree.
2. Inorder Traversal: Order: Left subtree -> Root node -> Right subtree.
3. Postorder Traversal: Order: Left subtree -> Right subtree -> Root node.

Reconstructing a Binary Tree from Preorder and Inorder Traversals

Given the preorder and inorder traversal sequences of a binary tree, the tree can be uniquely reconstructed. The specific steps are as follows:

Algorithm Steps

1. Determine the Root Node: The first element of the preorder traversal is the root node.
2. Partition the Left and Right Subtrees: Find the position of the root node in the inorder traversal. Elements to its left belong to the left subtree, and elements to its right belong to the right subtree.
3. Recursively Build the Left and Right Subtrees: Use the corresponding preorder and inorder sequences to recursively build the left and right subtrees.

Formula Representation

Let the preorder traversal be $P = [P_1, P_2, \ldots, P_n]$ and the inorder traversal be $I = [I_1, I_2, \ldots, I_n]$; then:

1. The root node is $R = P_1$.
2. Find the position of $R$ in the inorder traversal, denoted as $k$; then:
   • The inorder traversal of the left subtree is $I_L = [I_1, \ldots, I_{k-1}]$
   • The inorder traversal of the right subtree is $I_R = [I_{k+1}, \ldots, I_n]$
   • The preorder traversal of the left subtree is $P_L = [P_2, \ldots, P_{k}]$
   • The preorder traversal of the right subtree is $P_R = [P_{k+1}, \ldots, P_n]$

C Code Implementation

#include <stdio.h>
#include <stdlib.h>

// Define binary tree node structure
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Create new node
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

// Recursive function to build binary tree from preorder and inorder
TreeNode* buildTreePreIn(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (preorderSize == 0 || inorderSize == 0) {
        return NULL;
    }

    int rootVal = preorder[0];
    TreeNode* root = newNode(rootVal);

    int rootIndexInorder;
    for (rootIndexInorder = 0; rootIndexInorder < inorderSize; ++rootIndexInorder) {
        if (inorder[rootIndexInorder] == rootVal) {
            break;
        }
    }

    root->left = buildTreePreIn(preorder + 1, rootIndexInorder, inorder, rootIndexInorder);
    root->right = buildTreePreIn(preorder + 1 + rootIndexInorder, preorderSize - 1 - rootIndexInorder, inorder + rootIndexInorder + 1, inorderSize - 1 - rootIndexInorder);

    return root;
}

Reconstructing a Binary Tree from Postorder and Inorder Traversals

Similarly, given the postorder and inorder traversal sequences of a binary tree, the tree can also be uniquely reconstructed. The specific steps are as follows:

Algorithm Steps

1. Determine the Root Node: The last element of the postorder traversal is the root node.
2. Partition the Left and Right Subtrees: Find the position of the root node in the inorder traversal. Elements to its left belong to the left subtree, and elements to its right belong to the right subtree.
3. Recursively Build the Left and Right Subtrees: Use the corresponding postorder and inorder sequences to recursively build the left and right subtrees.

Formula Representation

Let the postorder traversal be $P = [P_1, P_2, \ldots, P_n]$ and the inorder traversal be $I = [I_1, I_2, \ldots, I_n]$; then:

1. The root node is $R = P_n$.
2. Find the position of $R$ in the inorder traversal, denoted as $k$; then:
   • The inorder traversal of the left subtree is $I_L = [I_1, \ldots, I_{k-1}]$
   • The inorder traversal of the right subtree is $I_R = [I_{k+1}, \ldots, I_n]$
   • The postorder traversal of the left subtree is $P_L = [P_1, \ldots, P_{k-1}]$
   • The postorder traversal of the right subtree is $P_R = [P_{k}, \ldots, P_{n-1}]$

C Code Implementation

// Recursive function to build binary tree from postorder and inorder
TreeNode* buildTreePostIn(int* postorder, int postorderSize, int* inorder, int inorderSize) {
    if (postorderSize == 0 || inorderSize == 0) {
        return NULL;
    }

    int rootVal = postorder[postorderSize - 1];
    TreeNode* root = newNode(rootVal);

    int rootIndexInorder;
    for (rootIndexInorder = 0; rootIndexInorder < inorderSize; ++rootIndexInorder) {
        if (inorder[rootIndexInorder] == rootVal) {
            break;
        }
    }

    root->left = buildTreePostIn(postorder, rootIndexInorder, inorder, rootIndexInorder);
    root->right = buildTreePostIn(postorder + rootIndexInorder, postorderSize - 1 - rootIndexInorder, inorder + rootIndexInorder + 1, inorderSize - 1 - rootIndexInorder);

    return root;
}

Can Preorder and Postorder Traversals Uniquely Determine a Binary Tree?

Preorder and postorder traversals cannot uniquely determine a binary tree. The reason is that preorder and postorder traversals alone cannot uniquely determine the left and right subtree structure of a node. For example, consider the following two different tree structures:

Tree 1:
    1
   /
  2
   \
    3

Tree 2:
    1
     \
      2
     /
    3

Both trees have identical preorder and postorder traversal sequences, but their structures are different. Therefore, preorder and postorder traversals alone cannot uniquely determine a binary tree.