Saving the in-order visit of a binary tree in an array

Question

The question is the following: is there an algorithm which, given an binary tree T and an array, allows to store in the array the result of the correspondent in-order visit of the tree?

Pseudo-code of a "normal" in-order visit:

inOrder(x){ // x is a node of a binary tree
   if(x != NIL){ // the node is not null
      inOrder(x.left)
      print(x.key)
      inOrder(x.right)
   }
}

// Function calling inOrder
printInOrder(T){ // T is a binary tree
   inOrder(T.root) // T.root is the root of the tree
}

Example: Given the following tree

     5 
   /   \
  3     8
 / \   / 
2   7 1   

the algorithm above should output 2 3 7 5 1 8.

I'm sure this can be achieved and it shouldn't be too hard but I'm currently struggling for this problem.

Answer 1

Writing to an array (instead of printing) means you need to keep track of which index to write at in the array. If you need to do this without any mutable state other than the array itself, you need to pass the current index as an argument, and return the new current index.

The code below is written in static single assignment form so even the local variables are not mutated. If that isn't required then the code can be simplified a bit. I'm assuming that the array length is known; if it needs to be computed, that is a separate problem.

inOrder(x, arr, i) {
    if(x == NIL) {
        return i
    } else {
        i2 = inOrder(x.left, arr, i)
        arr[i2] = x.key
        i3 = inOrder(x.right, arr, i2 + 1)
        return i3
    }
}

getArrayInOrder(T, n) {
    arr = new array of length n
    inOrder(T.root, arr, 0)
    return arr
}