Construct Binary Tree from Preorder and Inorder Traversal

Question

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Answer 1

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length == 0 || preorder.length != inorder.length) return null;
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
public TreeNode build(int[] pre, int start1, int end1, int[] in, int start2, int end2){
    if(start1 > end1 || start2 > end2) return null;
    int val = pre[start1];
    TreeNode cur = new TreeNode(val);
    int k = start2;
    for(; k <= end2; k++) 
        if(in[k] == val) break;
    cur.left = build(pre, start1 + 1, start1 + k - start2, in, start2, k - 1);
    cur.right = build(pre, start1 + k - start2 + 1, end1, in, k + 1, end2);
    return cur;
}

Answer 2

Hint:
A good way to attempt this question is to work backwards. Approach this question by drawing a binary tree, then list down its preorder and inorder traversal. As most binary tree problems, you want to solve this recursively.

About Duplicates:
In this solution, we will assume that duplicates are not allowed in the binary tree. Why?

Consider the following case:

preorder = [7, 7]
inorder =  [7, 7]

We can construct the following trees which are both perfectly valid solutions.

      7                     7
     /           or          \
    7                         7

Clearly, there would be ambiguity in constructing the tree if duplicates were allowed.

Solution:
Let us look at this example tree.

         _______7______
        /              \
     __10__          ___2
    /      \        /
    4       3      _8
             \    /
              1  11

The preorder and inorder traversals for the binary tree above is:

preorder = [7, 10, 4, 3, 1, 2, 8, 11]
inorder =  [4, 10, 3, 1, 7, 11, 8, 2]

The crucial observation to this problem is the tree's root always coincides with the first element in preorder traversal. This must be true because in preorder traversal you always traverse the root node before its children. The root node's value appear to be 7 from the binary tree above.

We easily find that 7 appears as the 4^th index in the inorder sequence. (Notice that earlier we assumed that duplicates are not allowed in the tree, so there would be no ambiguity). For inorder traversal, we visit the left subtree first, then root node, and followed by the right subtree. Therefore, all elements left of 7 must be in the left subtree and all elements to the right must be in the right subtree.

We see a clear recursive pattern from the above observation. After creating the root node (7), we construct its left and right subtree from inorder traversal of [4, 10, 3, 1] and [11, 8, 2] respectively. We also need its corresponding preorder traversal which could be found in a similar fashion. If you remember, preorder traversal follows the sequence of root node, left subtree and followed by right subtree. Therefore, the left and right subtree's postorder traversal must be [10, 4, 3, 1] and [2, 8, 11] respectively. Since the left and right subtree are binary trees in their own right, we can solve recursively!

We left out some details on how we search the root value's index in the inorder sequence. How about a simple linear search? If we assume that the constructed binary tree is always balanced, then we can guarantee the run time complexity to be O(N log N), where N is the number of nodes. However, this is not necessarily the case and the constructed binary tree can be skewed to the left/right, which has the worst complexity of O(N²).

A more efficient way is to eliminate the search by using an efficient look-up mechanism such as hash table. By hashing an element's value to its corresponding index in the inorder sequence, we can do look-ups in constant time. Now, we need only O(N) time to construct the tree, which theoretically is the most efficient way.

For illustration purpose, the below code uses a simple array for table look-up, which is restricted to elements of 0 to 255 only. You should be able to extend it easily to use a hash table.

const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
    for (int i = 0; i < n; i++) {
        assert(0 <= inorder[i] && inorder[i] <= MAX-1);
        mapIndex[inorder[i]] = i;
    }
}

// precondition: mapToIndices must be called before entry
Node *buildInorderPreorder(int in[], int pre[], int n, int offset) {
    assert(n >= 0);
    if (n == 0) return NULL;
    int rootVal = pre[0];
    int i = mapIndex[rootVal]-offset;  // the divider's index
    Node *root = new Node(rootVal);
    root->left = buildInorderPreorder(in, pre+1, i, offset);
    root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1, offset+i+1);
    return root;
}

Now, if we are given inorder and postorder traversal, can we construct the binary tree?

The answer is yes, using very similar approach as above. Please see question Construct Binary Tree from Inorder and Postorder Traversal for more details.

Further Thoughts:

If we are given preorder and postorder traversal, can we construct the binary tree? Why or why not?
Given preorder, inorder, and postorder traversal, how can you verify if these traversals are referring to the exact same binary tree?
Remember from my earlier post: Serialization/Deserialization of a Binary Tree? It is trivial to see this as an alternative method to serialize/deserialize a binary tree. :)

Answer 3

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
        return null;
    }

    // the first item in preorder is root
    TreeNode root = new TreeNode(preorder[0]);
    if (preorder.length == 1) {
        return root;
    }

    int i = 0;
    for (; inorder[i] != root.val; i++)
        ;

    if (i > 0) {
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, i + 1),
                Arrays.copyOfRange(inorder, 0, i));
    }
    if (i < inorder.length - 1) {
        root.right = buildTree(Arrays.copyOfRange(preorder, i + 1, preorder.length),
                Arrays.copyOfRange(inorder, i + 1, inorder.length));
    }

    return root;
}

Answer 4

/**Passed both small and large judge.
Not so many surprise here, just pay extra attention to the boundary indices.
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int> const& preorder, int const pre_first, int const pre_last,
      vector<int> const& inorder, int const in_first, int const in_last){
          if (in_first > in_last) return NULL;
          TreeNode* root = new TreeNode(preorder[pre_first]);
          if (in_first == in_last) return root;
          size_t const r_in = distance(inorder.begin(), 
            find(inorder.begin()+in_first, inorder.begin()+in_last, root->val));
          size_t const sizeLeft = r_in - in_first;//size of left subtree
          root->left = build(preorder, pre_first+1, pre_first+sizeLeft-1,
            inorder, in_first, r_in-1);
          root->right = build(preorder, pre_first+sizeLeft+1, pre_last,
            inorder, r_in+1, in_last);
          return root;
      }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return build(preorder, 0, preorder.size()-1,
          inorder, 0, inorder.size()-1);

    }
};

Answer 5

std::unordered_map<int,int> index_map;

void buildMap(vector<int> &inorder) {
    index_map.clear();
    for (int i = 0; i < inorder.size(); i++) {
        index_map[inorder[i]] = i;
    }
}

TreeNode *buildTreeInOrder(vector<int> &preorder, int pre_offset,
        vector<int> &inorder, int in_offset, int len) {
    if (!len)
        return NULL;

    cout << pre_offset << ", " << in_offset << ", " << len << endl;

    TreeNode *root = new TreeNode(preorder[pre_offset]);
    int i = index_map[preorder[pre_offset]];

    root->left = buildTreeInOrder(preorder,
            pre_offset+1, inorder, in_offset, i-in_offset);
    root->right = buildTreeInOrder(preorder,
            pre_offset+(i-in_offset)+1, inorder, in_offset+(i-in_offset)+1, len-(i-in_offset)-1);

    return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (preorder.size() == 0 && inorder.size() == 0) {
        return NULL;
    }

    buildMap(inorder);
    return buildTreeInOrder(preorder, 0, inorder, 0, preorder.size());
}

Answer 6

class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    int size = preorder.size();
    if(size == 0)
        return NULL;        
    return BuildBT(preorder, inorder, 0, 0, size-1);
}

TreeNode *BuildBT(vector<int> &preorder, vector<int> &inorder, int pos, int start, int end){
    if(start > end )
        return NULL;                    
    int j = std::find(inorder.begin()+start, inorder.end()+end, preorder[pos]) - inorder.begin();

    TreeNode *root = new TreeNode(inorder[j]);
    root->left = BuildBT(preorder, inorder, pos+1, start, j-1);
    root->right = BuildBT(preorder, inorder, j+pos-start+1, j+1, end); // j+pos-start+1 is the relative position in the preorder array of the  next right child   
    return root;
}

};

Answer 7

recursively construct left and right

public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { // Start typing your Java solution below // DO NOT write main() function

    if(inorder.length == 0 && postorder.length ==0){
        return null;
    }
    int root = postorder[postorder.length-1];
    int[] preOrderLeft;
    int[] postOrderLeft;
    int[] preOrderRight;
    int[] postOrderRight;
    TreeNode rootNode= new TreeNode(root);

    for(int i=0;i<inorder.length;i++){
        if(inorder[i] == root){

            preOrderLeft = Arrays.copyOfRange(inorder,0,i);
            postOrderLeft = Arrays.copyOfRange(postorder,0,i);
            rootNode.left = buildTree(preOrderLeft,postOrderLeft);

            if(i+1 < inorder.length && i+1<postorder.length){
            preOrderRight = Arrays.copyOfRange(inorder,i+1,inorder.length);
            postOrderRight = Arrays.copyOfRange(postorder,i,postorder.length-1);
            rootNode.right = buildTree(preOrderRight,postOrderRight);                
            }
            break;

        }
    }

    return rootNode;
}

}

Answer 8

1)the first node in preorder is the tree root;

2)find the root node in inorder, then get the left and right subtree order(both preorder and inorder list);

3)if can't find the root node in inorder, then the input is error, can not build the tree;

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(preorder.empty()) {
        return NULL;
    }
    TreeNode* root = NULL;
    if (!buildSubTree(root, preorder, 0, preorder.size(), inorder, 0, inorder.size())) {
        return NULL;
    }
    return root;
}

bool buildSubTree(TreeNode* &root, vector<int> &preorder, int prebegin, int preend, 
            vector<int> &inorder, int inbegin, int inend) {
    if (prebegin >= preend || inbegin >= inend) {
        return true;
    } else if (preend-prebegin != inend-inbegin) {
        return false;
    }
    root = new TreeNode(preorder[prebegin]);
    int root_index = inbegin;
    for (; root_index < inend; ++root_index) {
        if (inorder[root_index] == preorder[prebegin]) {
            break;
        }
    }
    if (root_index == inend) {
        //error 
        return false;
    }
    if (!buildSubTree(root->left, preorder, prebegin+1, prebegin+1+root_index-inbegin,
            inorder, inbegin, root_index)) {
        return false;
    }
    if (!buildSubTree(root->right, preorder, prebegin+1+root_index-inbegin, preend, 
            inorder, root_index+1, inend)) {
        return false;
    }
    return true;
}

Answer 9

Here is an O(n) iterative solution, using a Stack to keep track of where the subtree roots are.

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0 || preorder.length != inorder.length) return null;

    TreeNode root = new TreeNode(preorder[0]);
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    TreeNode cur = root;
    int preptr = 1;
    int inptr = 0;
    while (preptr < preorder.length) {
        boolean hasPopped = false;
        while (!stack.isEmpty() && inorder[inptr] == stack.peek().val) {
            cur = stack.pop();
            inptr++;
            hasPopped = true;
        }
        if (!hasPopped) {
            TreeNode newLeft = new TreeNode(preorder[preptr++]);
            stack.push(newLeft);
            cur.left = newLeft;
            cur = newLeft;
        } else {
            TreeNode newRight = new TreeNode(preorder[preptr++]);
            stack.push(newRight);
            cur.right = newRight;
            cur = newRight;
        }
    }
    return root;
}

Answer 10

reverse_idx is a hash table reversing the key and value of inorder.

class Solution {
    unordered_map<int,int> reverse_idx;
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        reverse_idx.clear();
        for(int i=0;i<inorder.size();++i){
            reverse_idx.insert(make_pair(inorder[i],i));
        }
        return buildTreeAux(preorder,0,0,inorder.size());
    }
    TreeNode * buildTreeAux(vector<int> &preorder,int pre_idx,int inorder_start,int n){
        if(n==0 || pre_idx==preorder.size()) return NULL;
        int root_val=preorder[pre_idx];
        int root_idx=reverse_idx[root_val];
        TreeNode *root=new TreeNode(root_val);
        int n_left = root_idx-inorder_start;
        root->left=buildTreeAux(preorder,pre_idx+1,inorder_start,n_left);
        root->right=buildTreeAux(preorder,pre_idx+n_left+1,root_idx+1,n-n_left-1);
        return root;
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

Follow this question

Welcome to LeetCode

Related questions