Given the pre-order and in-order traversing result of a binary tree, write a function to rebuild the tree. 5 AnswersHere is the algorithm (I am too lazy to write the whole program). Let's number the nodes of in-order traversing sequentially (1,2,3, etc.). Then take the list of nodes of pre-order traversing. The first one is the root. While their numbers (from in-order list) decreasing, connect them as left-hand children, one by one. If the next number is greater, find the node with the max number (less than this one) and connect this one to it as right-hand child. Etc. I think they meant any "binary tree" not a binary search tree; but ALL values must be different (imagine a tree with n 1's; it has a Catalan(n) configurations and the same pre- and in-order traversals). So here is a solution: node* rec(const std::vector& PRE, const std::vector& IN) { node * r = new node(0,PRE[0]); // root node * v = r; // what we want to return bool l = PRE[0] != IN[0]; // do I go left? std::set path; // ancestors path.insert(PRE[0]); for(int p=1, i=l ? 0 : 1; p!=(int)PRE.size(); ++p) { node * n = new node(r,PRE[p]); r = l ? r->_left = n : r->_right = n; l = true; // revert to left if (PRE[p] == IN[i]) { // must go right or up ++i; while(i _v); r = r->_up; if (r->_v == IN[i]) { ++i; break; } } } } } path.insert(PRE[p]); } return v; } The idea is that the pre-order is basically a depth-first search order, which is convenient to build the tree (it is always connected at every interim stage). The in-order is used to decide whether to move right or up. BTW, you can guess the definition of "node". I have done something in Java. Maybe this might help: import java.util.Arrays; import java.util.TreeMap; import javax.management.RuntimeErrorException; public class BinaryTrees { public static class Node { Node right; Node left; char value; // preorder // public String toString() { // return (value + " ") + (this.left == null ? "" : this.left) // + (this.right == null ? "" : this.right); // // } // in order // public String toString() { // return (this.left == null ? "" : this.left) +(value + " ") + // (this.right == null ? "" : this.right); // // } // post order public String toString() { return (this.left == null ? "" : this.left) + "" + (this.right == null ? "" : this.right) + (value + " "); } } private static final char[] preOrderStr = new char[] { 'u','f','A','C','M','h','s','9','6' }; private static final char[] inOrderStr = new char[] { 'A','f','C','u','s','h','M','9','6' }; public static void main(String... args) { BinaryTrees trees = new BinaryTrees(); Node root = trees.rebuildTree(inOrderStr, preOrderStr); System.out.println(root); } public Node rebuildTree(char[] inOrderS, char[] preOrderS) { Node root = new Node(); root.value = preOrderS[0]; int index = getIndex(inOrderS, root.value); char[] leftInOrderS = new char[index]; char[] rightInOrderS = new char[inOrderS.length - index - 1]; char[] leftPreOrderS = new char[index]; char[] rightPreOrderS = new char[preOrderS.length - index - 1]; System.arraycopy(inOrderS, 0, leftInOrderS, 0, index); System.arraycopy(inOrderS, index + 1, rightInOrderS, 0, inOrderS.length - index - 1); System.arraycopy(preOrderS, 1, leftPreOrderS, 0, index); System.arraycopy(preOrderS, index+1, rightPreOrderS, 0, preOrderS.length - index -1); if (leftInOrderS.length != 0 && leftPreOrderS.length != 0) root.left = rebuildTree(leftInOrderS, leftPreOrderS); if (rightInOrderS.length != 0 && rightPreOrderS.length != 0) root.right = rebuildTree(rightInOrderS, rightPreOrderS); return root; } public int getIndex(char[] chars, char ch) { for (int i = 0; i < chars.length; i++) if (ch == chars[i]) return i; throw new RuntimeException("No char " + ch + " in the vector"); } } Show More Responses package datastructures.trees; public class BuildTreeInorderPreorder { public static void buildTree(int[] inorder, int[] preorder) { TreeNode root = createNode(preorder,inorder,0,preorder.length-1,0,inorder.length - 1); printPostOrder(root); } private static TreeNode createNode(int[] preorder, int[] inorder, int ps, int pe, int is, int ie) { if(ps > pe || is > ie) { return null; } TreeNode newNode = new TreeNode(preorder[ps]); int i; for(i = is; i <= ie; i++) { if(preorder[ps] == inorder[i]) { break; } } newNode.left = createNode(preorder, inorder, ps + 1, ps + i - is, is, i - 1); newNode.right = createNode(preorder, inorder, ps + i - is + 1, pe, i + 1, ie); return newNode; } private static void printPostOrder(TreeNode node) { if(node == null) { return; } printPostOrder(node.left); printPostOrder(node.right); System.out.print(node.x + ""); } public static void main(String[] args) { int[] preorder = {1,2,4,7,8,5,3,6,9,10,11,12}; int[] inorder = {7,4,8,2,5,1,3,9,6,10,12,11}; buildTree(inorder,preorder); } } class TreeNode { int x; TreeNode left, right; public TreeNode(int x) { this.x = x; } } Here is a compact solution using recursion. Assume your pre-ordering is given in "pre", and in-ordering is given in "in", in the form of integers from 1 to n, representing nodes. "p" is an indicator showing which of the pre-order nodes we're currently procesing, and "ind" is used to quickly find where a node is in "in". class Node { int value=-1; Node left=null, right=null; public Node(int val){value=val;} public Node(int val, Node l, Node r){value=val;left=l;right=r;} } public class Rebuild { int[] pre, in,ind; int p=-1; public Node reconstruct(int st, int ed) { p++; //go to next root if(st==ed)return new Node(pre[p]); Node lr=reconstruct(st,ind[p]-1); Node rr=reconstruct(ind[p]+1,ed); return new Node(pre[p],lr,rr); } public static void main(String[] args) { //input "pre" and "in" however you want, initialise ind for(int i=0;i |