Binary tree from pre-order and workaround

Question

How can I get a tree view of this pre-path along the way:

Pre: A, B, D, E, C, F, G, H in: E, D, B, A, G, F, H, C

EDITED: MY answer

A / \ BC / \ DF / / \ EGH 

Answer 1

EDIT: Correction,

You do not have the correct answer, FGH is to the left of C.

To check how to run both algorithms, follow these steps:

 PreOrder(node) if node is null return Print(node) PreOrder(node.left) PreOrder(node.Right) InOrder(node) if node is null return InOrder(node.left) Print(node) InOrder(node.Right) 

You know that A is the root because it starts pre-ordering. Use the ordered nodes to the left and right of A. B is the second node (pre-order) and to the left of A (in order), etc.

You know that F, G, H is left from C due to order in order.

Basically, use pre-order to select the next node and in order to see if it is to the left or right of the parent node.

EDIT (April 18, 2011) :

To show how mechanical this process is, I suggest this pseudo-code:

 // Add method on binary tree class -- stock standard method Add(item, comparer) newNode = new Node(item) parent = null // Find suitable parent currentNode = root while currentNode is not null parent = currentNode if comparer(newNode.Key, currentNode.Key) < 0 currentNode = currentNode.Left else currentNode = currentNode.Right // Add new node to parent if parent is null root = newNode else if comparer(newNode.Value, parent.Value) < 0 parent.Left = newNode else parent.Right = newNode 

The trick is to use the sequence in order to determine if the node is being added to the left or right of its parent, for example:

 // Client code // Input arrays var preOrder = ["A","B","D","E","C","F","G","H"] var inOrder = ["E","D","B","A","G","F","H","C"] // A collection associating the Key value with its position in the inOrder array var inOrderMap = GetInOrderMap(inOrder) // Build tree from pre-order and in-order sequences foreach (item in preOrder) Add(item, fun (l, r) -> inOrderMap[l] - inOrderMap[r]) 

I am going through lamba, but any equivalent method for going through a comparator should do.

Answer 2

Here is a mathematical approach to achieving things in a very simplified way:

Used language: Java

`
/ * Algorithm for building a binary tree from specified Inorder and Preorder traversals. The following is the terminology:

i: represents the inorder array supplied

p: represents the presented array of pre-orders

beg1: starting index of the inorder array

beg2: starting index of the preorder array

end1: end index of inorder array

end2: end index of the preorder array

* /

public static void constructTree (Node root, int [] i, int [] p, int beg1, int end1, int beg2, int end2)

{

 if(beg1==end1 && beg2 == end2) { root.data = i[beg1]; } else if(beg1<=end1 && beg2<=end2) { root.data = p[beg2]; int mid = search(i, (int) root.data); root.left=new Node(); root.right=new Node(); constructTree(root.left, i, p, beg1, mid-1, beg2+1, beg2+mid-beg1); System.out.println("Printing root left : " + root.left.data); constructTree(root.right, i, p, mid+1, end1, beg2+1+mid-beg1, end2); System.out.println("Printing root left : " + root.right.data); } 

}

`

You need to call the function by executing the following code:

 int[] i ={4,8,7,9,2,5,1,6,19,3,18,10}; //Inorder int[] p ={1,2,4,7,8,9,5,3,6,19,10,18}; //Preorder Node root1=new Node(); constructTree(root1, i, p, 0, i.length-1, 0, p.length-1); 

If you need a more detailed explanation of the code, please indicate it in the comments. I would be happy to help :).

Answer 3

Below is a working implementation in C #

 public static class TreeUtil { public static BinarySearchTree<T> FromTraversals<T>(T[] preorder, T[] inorder) { if (preorder == null) throw new ArgumentNullException("preorder"); if (inorder == null) throw new ArgumentNullException("inorder"); if (preorder.Length != inorder.Length) throw new ArgumentException("inorder and preorder have different lengths"); int n = preorder.Length; return new BinarySearchTree<T>(FromTraversals(preorder, 0, n - 1, inorder, 0, n - 1)); } public static BinaryTreeNode<T> FromTraversals<T>(T[] preorder, int pstart, int pend, T[] inorder, int istart, int iend) { if (pstart > pend) return null; T rootVal = preorder[pstart]; int rootInPos; for (rootInPos = istart; rootInPos <= iend; rootInPos++) //find rootVal in inorder if (Comparer<T>.Default.Compare(inorder[rootInPos], rootVal) == 0) break; if (rootInPos > iend) throw new ArgumentException("invalid inorder and preorder inputs"); int offset = rootInPos - istart; return new BinaryTreeNode<T>(rootVal) { Left = FromTraversals(preorder, pstart + 1, pstart + offset, inorder, istart, istart + offset - 1), Right = FromTraversals(preorder, pstart + offset + 1, pend, inorder, istart + offset + 1, iend), }; } } 

Here is one possible implementation of BinarySearchTree<T> and BinaryTreeNode<T> . Some tests:

 [TestMethod] public void TestGenerationFromTraversals() { var preorder = new[] {1, 2, 4, 5, 3}; var inorder = new[] {4, 2, 5, 1, 3}; AssertGenerationFromTraversal(preorder, inorder); var preorder2 = new[] { 'A', 'B', 'D', 'E', 'C', 'F' }; var inorder2 = new[] { 'D', 'B', 'E', 'A', 'F', 'C' }; AssertGenerationFromTraversal(preorder2, inorder2); } private static void AssertGenerationFromTraversal<T>(T[] preorder, T[] inorder) { var tree = BinarySearchTreeUtil.FromTraversals(preorder, inorder); var treeInorder = new List<T>(); tree.TraverseInOrder(treeInorder.Add); var treePre = new List<T>(); tree.TraversePreOrder(treePre.Add); Assert.IsTrue(preorder.SequenceEqual(treePre)); Assert.IsTrue(inorder.SequenceEqual(treeInorder)); }