Build Binary Tree from Array Traversal Result

From a tree, you can traversal it with preorder, inorder and post order (DFT) or level by level. You can not restore a tree from only one of result without extra information, but you have chance to restore it with two types of result.

For example, most common one is to restore a binary tree from preorder and inorder results.

In preorder, first element is the root, then entire left tree and then entire right tree.
In inorder, root is somewhere in the middle, left to it is entire left tree, right to it is entire right tree. you can use root from preorder to locate its position in an inorder array.

And with root position in in-order array, number of elements in left tree can be figured out, with this information, boundary of preorder's left and right subtrees can be extracted out.

Since each node is also a tree, then recursively applying this algorithm, it will be able to find children for all parents.




Preorder and post order won't work, because it can not find out root.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

public static TreeNode rebuildBinaryTreeRec(List<Integer> preOrder, List<Integer> inOrder){ TreeNode root = null; List<Integer> leftPreOrder; List<Integer> rightPreOrder; List<Integer> leftInorder; List<Integer> rightInorder; int inorderPos; int preorderPos; if ((preOrder.size() != 0) && (inOrder.size() != 0)) { // first element in preorder array is root root = new TreeNode(preOrder.get(0)); // Based upon the root information, manupulate preorder array to separate it into left and right subarrays // find root according to root in preorder inorderPos = inOrder.indexOf(preOrder.get(0)); leftInorder = inOrder.subList(0, inorderPos); rightInorder = inOrder.subList(inorderPos + 1, inOrder.size()); //then according to in order sub tree information, help preorder to determine the left and right tree preorderPos = leftInorder.size(); leftPreOrder = preOrder.subList(1, preorderPos + 1); rightPreOrder = preOrder.subList(preorderPos + 1, preOrder.size()); //then root's left subtree is the subtree built from left preorder and left inorder subtrees root.left = rebuildBinaryTreeRec(leftPreOrder, leftInorder); //root's right tree is the tree built from right part of preorder subtree and right part of in order subtree root.right = rebuildBinaryTreeRec(rightPreOrder, rightInorder); } //return the root of subtrees return root; }