CareerCup

type 'a tree = 
    | Leaf of 'a 
    | Tree of 'a tree list

let flatten tree = 
    let rec aux root acc = match root with 
        | [] -> acc
        | Leaf x::t -> aux t (x::acc)
        | Tree h::t -> aux t (aux h acc)
    in List.rev(aux tree []);;

flatten [ Tree [ Leaf 1; Leaf 2 ; Tree [ Leaf 3 ; Tree [ Leaf 4 ]]]];;

OCaml and other functional languages were made for this problem.

In a C program, I would use a qualified union, which is the alternative in an imperative language.

typedef struct _Tree {
      int tell;
      int branch_count;
      union _Data {
            int num;
            struct _Tree *branches;
      } Data;
} Tree;

}

I believe the size of the union is the size of the largest of its elements, where the union can only be one of the elements at any one time; hence, it can either be a pointer to its first branch, or it can be a leaf's data. The tell int determines if it is a leaf or a node with branches. If it does have branches, num_branches determines how many.

This approach doesn't seem to be constant space. It's linear space - i.e. creating a new array that's within a constant of n, the length of the original array.
If the array isn't sorted, this cannot be done in linear time, so I'm assuming that the array is sorted.
Sorry I'm just a little confused by the question. Am I way off base here?

Yeah, I think this is what they were looking for. Thanks!

As I said above, you do not get a string as an input