Title: Reconstruct a binary tree from its preorder and inorder traversals in C#

If the nodes in a binary tree don't contain any repeated values, then you can reconstruct the tree from its preorder and inorder traversals. (In fact that was part the final exam for the first algorithms course I ever took back in the early 1980s!)

Algorithm

The idea is relatively simple. The first node in the preorder traversal is the tree's root node, so you use that to figure out what the root is.

Next, you search the inorder traversal for the root node's value. Because this is an inorder traversal, everything to the left is part of the left branch out of the root node and everything to the right is part of the right branch. You use the lengths of those sub-traversals to find the corresponding sub-traversals in the preorder traversal.

After you find the traversals for the left and right subtrees, you use the same technique recursively to reconstruct the left and right subtrees.

For example, the picture on the right shows the example tree. We start with preorder and inorder traversals { ABDGECFHI, GDBEACHFI }. (See the picture at the top of the post.)

The first value in the preorder traversal tells us that A is the root node.

Next we find A in the inorder traversal. The strings to the left and right of A are GBDE and CHFI, so those are the inorder traversals of the left and right subtrees.

The left inorder subtree traversal has length four, so that subtree's preorder traversal must also have length four. That means the next four characters in the original preorder traversal is the left subtree's traversal: BDGE.

The right subtree's inorder traversal also has length four, so its preorder traversal incldues the next four characters: CFHI.

Now we have the preorder and inorder traversals for the subtrees: { BDGE, GBDE } and { CFHI, CHFI }. We use the same technique to rebuild the subtrees.

Code

Here's the source code.

private Node ReconstructTree( string preorder, string inorder) { Node root = new Node(preorder[0].ToString()); int pos = inorder.IndexOf(preorder[0]); string inorder1 = inorder.Substring(0, pos); string inorder2 = inorder.Substring(pos + 1); string preorder1 = preorder.Substring(1, inorder1.Length); string preorder2 = preorder.Substring(inorder1.Length + 1); if (inorder1.Length > 0) { root.Left = ReconstructTree(preorder1, inorder1); } if (inorder2.Length > 0) { root.Right = ReconstructTree(preorder2, inorder2); } return root; }

The method takes the preorder and inorder traversals as parameters and returns the tree that they represent.

The method first gets the root node's value and makes a node to hold that value.

Next the code finds the root's value within the inorder traversal. It gets the inorder traversals to the left and right of that value and uses their lengths to get the left and right preorder traversals.

If the left traversals have non-zero length, the method calls itself recursivelty to rebuild the left subtree and attaches it to the root node. Similarly, if the right traversals have non-zero length, the method calls itself recursivelty to rebuild the right subtree and attaches it to the root node.

The method finishes by returning the root node and any subtrees that it may contain.

For more information about trees, traversals, and more exotic data structures, see my book Essential Algorithms, Second Edition.

Download the example to experiment with it and to see additional details.