reconstructing binary tree from inorder and preorder

1
votes

I am trying to build a binary tree from:

• Preorder: A B C D E F G H I J K L M
• Inorder: C E D F B A H J I K G M L

I am almost positive the left half of the tree is correct, but the right half just does not seem right.

Can anyone see if they can figure out where my issue is?

I know preorder is Parent, Left, Right and that inorder is Left, Parent, Right

What do I need to do to make sure this tree is correct?

Binary Tree

2
algorithmtreebinary-tree
Possible duplicate of reconstructing a tree from its preorder and postorder lists - Matt Timmermans

2 Answers

1
votes

You can apply following algorithm with your preorder and inorder traversal. The resulting tree will always be valid and unique.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

TreeNode *treeBuilder(vector<int> &preorder, vector<int> &inorder, int start, int end, int indx) {
    if(start > end) return nullptr;

    TreeNode *root = new TreeNode(preorder[indx]);
    int rootPosition;    
    for(int i = start; i <= end; ++i) {
        if(inorder[i] == root->val) {
            rootPosition = i;
            break;
        }
    }
    root->left = treeBuilder(preorder, inorder, start, rootPosition - 1, indx + 1);
    root->right = treeBuilder(preorder, inorder, rootPosition + 1, end, indx + 1 + rootPosition - start);
    return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    if(preorder.size() == 0) return nullptr;
    return treeBuilder(preorder, inorder, 0, inorder.size() - 1, 0);
}

I will add explanation if you feel difficulties to understand.

Edit

Applying above algorithm I mentioned on the given inorder and preorder sequences, The resulting tree is given below -

enter image description here

1
votes

A similar way, but using two indexes for the inorder array is as follows:

/* keys are between l_p and r_p in the preorder array

   keys are between l_i and r_i in the inorder array
 */
Node * build_tree(int preorder[], long l_p, long r_p,
          int inorder[], long l_i, long r_i)
{
  if (l_p > r_p)
    return nullptr; // arrays sections are empty

  Node * root = new Node(preorder[l_p]); // root is first key in preorder
  if (r_p == l_p)
    return root; // the array section has only a node

  // search in the inorder array the position of the root
  int i = 0;
  for (int j = l_i; j <= r_i; ++j)
    if (inorder[j] == preorder[l_p])
      {
        i = j - l_i;
        break;
      }

  root->left = build_tree(preorder, l_p + 1, l_p + i, 
              inorder, l_i, l_i + (i - 1));
  root->right = build_tree(preorder, l_p + i + 1, r_p, 
               inorder, l_i + i + 1, r_i);

  return root;
}