Flattening a binary tree to an array in Java

Question

I found this code for flattening a binary tree into array in Java. I am having hard time understanding how it works. Here is the code: ``` private static int FlattenTreeIntoArray(Node tree, int[] array, int i) { if (tree == null) return i; // Flatten left subtree i = FlattenTreeIntoArray(tree.Left, array, i); // Get data from the current node array[i] = tree.Data; // Flatten right subtree i = FlattenTreeIntoArray(tree.Right, array, i + 1); return i; } ``` My questions are as follows: This is the helper method, how is the real method actually called, or what is passed as parameters (`int[] array` and `int i`)? We do not know the size of binary tree. How does the method work? When the `tree` is `null`, it returns `i`. What does that mean? How does the flattening happen? Why `i+1` is passed to `right tree` but `i` to `left tree`? If you could demonstrate with this binary tree, it will be easy to follow:

Accepted Answer

This is a simple recursive example, once you understand this, all recursive tree algorithms should begin to make sense. I will try to answer your questions as best I can:

This is the helper method, how is the real method actually called, or what is passed as parameters to int i and int[] array -- we do not know the size of binary tree

Looking at the code, and since this is an interview type question, we will assume that the int[] array is big enough to fit everything.

`i` appears to be the current index of the array to populate so the first call to flatten the tree will be to set `i` to 0.

This method also returns an integer which is the number of elements that have been populated so far. This means that the final return will return the full length of the tree (and the number of elements populated in the array)

```
int[] array = new int[size];
Node root = ...
int bytesWritten = FlattenTreeIntoArray(root, array, 0);

//bytesWritten should equal size
assert(bytesWritten == size);
```

How does the method function: when the tree is null, it returns i. what does that mean?

This assumes that a `Node`'s left or right fields point to null if there is no child. Since we are using `i` to maintain where we are in the array, if there is no child, we don't update the value of `i`.

how does the flattening happens? why i+1 is passed to right tree but i to left tree. The flattening happens by finding the left most node and putting it in `i`. Then finding the next most left node and putting it in `i+1` etc.

Let's walk through the tree example you gave:

node= 8 i =0; array = {}

get left node of root, which is 3 and recursively call this flatten method, which gets the left node of 3 which is 1 and recursively calls the flatten method again, when gets the left node of 1 which is null. returns `i` = 0. Now we are in the flatten method for Node 1 `array[0] = Node 1's value` = `array[0] = 1.

Now call node 1's right field and flatten that incrementing i. Node 1's right field is null so we return the current value of i (which is 1).

Now we are back in node 1's flatten method and have finsished recurssing the left and right and have reached the end of the method so we return the current value of `i` which is 1.

Now we are back in the flatten method for node 3. We have just finished calling the flatten method for the left field which returned a value of 1 which is now what we set i to.

Now we update the array with node 3's value

```
array[1] = 3;
```

Now we flatten Node 3's right field (Node 6) with the incremented i so `i=2`

etc

Hope that helps

Flattening a binary tree to an array in Java

Solution

Problem