CareerCup

def printInorderFromPreorderStackVersion(nums):
    stack = [];
    stack.append(nums[0]);
    index = 1;
    while index < len(nums):
          if len(stack) == 0 or stack[len(stack) - 1] > nums[index]:
             stack.append(nums[index]);
          else:
            while len(stack) != 0 and stack[len(stack) - 1] < nums[index]:
                  print stack.pop();
            stack.append(nums[index]); 
          index = index + 1;
    
    
nums = [8, 4, 2, 6, 18, 10, 20]
print(printInorderFromPreorderStackVersion(nums));

Interesting question:
1) simplest approach any bst when walked in order returns the element in sorted order so simply sort them. Takes NlogN time and logn memory depending on sorting algo
2) Recursively find the next element by going left, root and right and following BST properties by keeping a track of min and max element at any node. Takes n memory and n time.

public class PreOrderToInOrderConverter {

// simplest solution
  public int[] printInorder(int[] nums) {
    if(nums == null|| nums.length <= 1) {
      return nums;
    }

    return Arrays.sort(nums);
  }

 // N time and n memory
  public int[] printInorder_better(int[] nums) {
    if(nums == null|| nums.length <= 1) {
      return nums;
    }

    LinkedList<Integer> result = new LinkedList<>();
    int minValue = Integer.MIN_VALUE;
    int maxValue = Integer.MAX_VALUE;
    this.getInOrderTraversal(nums, 0, minValue, maxValue, result);
    return result.toArray(); // just to return the array otherwise we could have returned the list itself
  }

  private int getInOrderTraversal(int[] nums, int index, int minValue, int maxValue, LinkedList<Integer> result) {
    if(index == nums.length) {
      return index;
    }
    int root = nums[index];
    // Left child is possible
    if(index + 1 < nums.length && root >= nums[index + 1] && nums[index + 1] > minValue) {
      index = getInOrderTraversal(nums, index + 1, minValue, root, result);
    }
    // add the root
    result.add(root);
    // right child is possible
    if(index + 1 < nums.length && root < nums[index + 1] && nums[index + 1] <= maxValue) {
      index = getInOrderTraversal(nums, index + 1, root, maxValue, result);
    }
    return index + 1;
  }
}

def printInorderFromPreorder(nums, start, end):
    if start == end:
        list = [nums[start]];
        return list;
    if start > end:
        return [];
    root = nums[start];
    breakPoint = 0;
    for i in range(start + 1, end + 1):
        if nums[i] > root:
           breakPoint = i; 
           break; 
    left = printInorderFromPreorder(nums, start + 1, breakPoint - 1);
    left.append(root);
    right = printInorderFromPreorder(nums, breakPoint, end);
    left.append(right);
    return left;

nums=[5, 2, 1, 3, 8, 6, 10]
print(printInorderFromPreorder(nums, 0, len(nums)-1));

# 1) assume the BST constraint is:
#    all values in left sub-tree (L) < value of root node < all values in right sub-tree
#    a preorder traversal looks like this T{L}{R}
#    an inorder traversal looks like this {L}T{R}
#    {L} is a sequence of integers that satisfy L < T, ...
# 2) use the array as source (with index s) and destination (with index d), start with s=0, d=0
#    let aux(s, d, pv) be a function that returns s, d after a sub-tree has been re-ordered 
#    to in-order with pv=value of parent node
#    - start condition aux(0, 0, +infinity)
#    - aux: 
#      > let v = array[s] (value of the node/sub-tree)
#      > if array[s+1] < v, recurse on (s+1, d, v) for left subtree
#      > place array[d] = v (inorder: place the value between left and right sub-tree)
#      > if array[s+1] < pv (the value of the parent node): recure on (s, d, pv) for right sub-tree
# 3) done
#
# space complexity: O(h), where h is the height of the BST (stack size)
# time complexity: O(n)

def fromPreOrderToInOrder(nums):
    def aux(nums, s, d, pv): #s: source, d: destination, pv: parent-value
        v = nums[s] 
        s += 1 
        if s < len(nums) and nums[s] < v: 
            s, d = aux(nums, s, d, v)                             
        nums[d] = v
        d += 1         
        if s < len(nums) and nums[s] < pv:
            s, d = aux(nums, s, d, pv)        
        return s, d    
    aux(nums, 0, 0, float('inf'))

Construct a BST using pre order and then print in order

#include <cstdlib>

#include <iostream>
using namespace std;

#include <iostream>
#include <functional>
#include <string>
#include<map>


struct node {
    node *left, *right;
    int value;
    node (int v) : value(v), left(NULL), right(NULL) {}
};

node *construct_tree(int *ara, int l, int h) {
    if (l > h) {
        return NULL;
    }

    node *root = new node(ara[l]);
    // find where the next larger is found
    int c = l+1;
    while(c <= h  && ara[c] <= ara[l]) {
        c++;
    }
    // c is not at the index which stands at the next right subtree.
    root->left = construct_tree(ara, l+1, c-1);
    root->right = construct_tree(ara, c, h);
    return root;
    
}

void print_tree(node *r) {
    if (!r) {
        return;
    }

    print_tree(r->left);
    cout << r->value << "\t";    
    print_tree(r->right);
}


int main() {
	// your code goes here
    int ara[] = {10, 5, 1, 7, 40, 50};
    node * root = construct_tree(ara, 0, sizeof(ara)/sizeof(ara[0]) -1);
    print_tree(root);
	return 0;
}

We can also use the min stack over the pre order seqeunce.
If the current element from array is less than the stack.top() insert
else continuing popping the stack and print these pop elements,
and insert the current element.

function transformPreToIn(order) {
  
  if (order.length <= 1) {
    return order;
  }
  
  var root = order[0];
  var left = order.filter(function(element){return element < root});
  var right = order.filter(function(element){return element > root});
    
  return transformPreToIn(left).concat(root, transformPreToIn(right));
  
}

var testcase1 = [10, 5, 1, 7, 40, 50];

console.info(transformPreToIn(testcase1));

function transformPreToIn(order) {
  
  if (order.length <= 1) {
    return order;
  }
  
  var root = order[0];
  var left = order.filter(function(element){return element < root});
  var right = order.filter(function(element){return element > root});
    
  return transformPreToIn(left).concat(root, transformPreToIn(right));
  
}

var testcase1 = [10, 5, 1, 7, 40, 50];

console.info(transformPreToIn(testcase1));

we just need to sort the array.
inorder return the values of the tree from the minimum to maximum.