Constructing a binary tree from its in-order and pre-order/post-order traversals

main.c

#include <stdio.h>
#include <string.h>
#include "node.h"

int main(void) {
  Node *binary_tree = new_node('A',
    new_node('B',
      new_node('D', NULL, NULL),
      new_node('E',
        new_node('G', NULL, NULL),
        NULL)),
    new_node('C',
      new_node('F', NULL, NULL),
      new_node('H', NULL, NULL)));
  printf("Original Binary Tree\n====================\n");
  print_binary_tree(binary_tree);
  delete_node(binary_tree);
  printf("\nBinary tree reconstructed from pre-order and in-order traversal"
    "\n===============================================================\n");
  const char *preorder = "ABDEGCFH", *inorder = "DBGEAFCH", *postorder = "DGEBFHCA";
  const size_t SIZE = strlen(inorder);
  binary_tree = binary_tree_from_preorder_inorder(preorder, inorder, SIZE);
  print_binary_tree(binary_tree);
  delete_node(binary_tree);
  printf("\nBinary tree reconstructed from in-order and post-order traversal"
    "\n================================================================\n");
  binary_tree = binary_tree_from_inorder_postorder(inorder, postorder, SIZE);
  print_binary_tree(binary_tree);
  delete_node(binary_tree);
  return 0;
}

node.c

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

Node *new_node(char data, Node *left, Node *right) {
  Node *nd = malloc(sizeof(Node));
  nd->data = data;
  nd->left = left;
  nd->right = right;
  return nd;
}

void delete_node(Node *nd) {
  if (nd != NULL) {
    delete_node(nd->left);
    delete_node(nd->right);
    free(nd);
  }
}

void print_preorder(const Node *nd) {
  if (nd != NULL) {
    printf("%c ", nd->data);
    print_preorder(nd->left);
    print_preorder(nd->right);
  }
}

void print_inorder(const Node *nd) {
  if (nd != NULL) {
    print_inorder(nd->left);
    printf("%c ", nd->data);
    print_inorder(nd->right);
  }
}

void print_postorder(const Node *nd) {
  if (nd != NULL) {
    print_postorder(nd->left);
    print_postorder(nd->right);
    printf("%c ", nd->data);
  }
}

void print_binary_tree(const Node *nd) {
  printf("Pre-order: ");
  print_preorder(nd);
  printf("\nIn-order: ");
  print_inorder(nd);
  printf("\nPost-order: ");
  print_postorder(nd);
  printf("\n");
}

Node *binary_tree_from_preorder_inorder(const char *preorder, const char *inorder, size_t size) {
  if (size == 0)
    return NULL;
  char data = preorder[0];
  size_t inorder_pos = -1;
  for (size_t i = 0; i < size; ++i)
    if (inorder[i] == data)
      inorder_pos = i;
  return new_node(data,
    binary_tree_from_preorder_inorder(preorder + 1, inorder, inorder_pos),
    binary_tree_from_preorder_inorder(preorder + 1 + inorder_pos, inorder + 1 + inorder_pos, size - inorder_pos - 1));
}

Node *binary_tree_from_inorder_postorder(const char *inorder, const char *postorder, size_t size) {
  if (size == 0)
    return NULL;
  char data = postorder[size - 1];
  size_t inorder_pos = -1;
  for (size_t i = 0; i < size; ++i)
    if (inorder[i] == data)
      inorder_pos = i;
  return new_node(data,
    binary_tree_from_inorder_postorder(inorder, postorder, inorder_pos),
    binary_tree_from_inorder_postorder(inorder + inorder_pos + 1, postorder + inorder_pos, size - inorder_pos - 1));
}

node.h

#ifndef NODE_H_
#define NODE_H_

/*
 * node.h
 * Header file for binary tree related declarations
 */

// Definition of a node of a binary tree
typedef struct node {
  char data;
  struct node *left, *right;
} Node;

// Binary tree constructor
Node *new_node(char, Node *, Node *);

// Binary tree destructor
void delete_node(Node *);

// Print a binary tree pre-order
void print_preorder(const Node *);

// Print a binary tree in-order
void print_inorder(const Node *);

// Print a binary tree post-order
void print_postorder(const Node *);

// Print a binary tree using all 3 traversal orders
void print_binary_tree(const Node *);

// Construct a binary tree from its corresponding pre-order and in-order traversals
Node *binary_tree_from_preorder_inorder(const char *, const char *, size_t);

// Construct a binary tree from its corresponding in-order and post-order traversal
Node *binary_tree_from_inorder_postorder(const char *, const char *, size_t);

#endif