# Building a tree with the heap property from an array and preserving its order

How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array?

For example, if I have:

2 1 5 6 2 3

I want to build:

  1
/ \
2   2
/ \
5   3
\
6


Because it has the heap property and its inorder is the original array 2 1 5 6 2 3.

• Just as a pointer, note that you want to construct treaps. Given an array with $a[i] = b_i$, you want the treap of values $i$ with priorities $b_i$. This proves that such a tree always exists and that it's unique (a simple induction). Also, you can just reuse treap operations -- but it won't be as efficient since you don't get the same average costs (your priorities aren't random). – Raphael Jul 23 '17 at 10:27

I have found a solution in ${\cal O}(n \log n)$. We could sort the array tracking the original index of every element in ${\cal O}(n\log n)$. In the original 2 1 5 6 2 3 example:

Sorted array:     1 2 2 3 5 6
Original indexes: 1 0 4 5 2 3


And now, we could insert the sorted elements on a binary tree in order. We insert the first element on the root, and then, we compare every element's index with the root's one to decide if we insert it on the left or the right subtree. The building process would be something like this:

First and second steps:

1(1)
/
2(0)

Third and fourth steps:

1(1)
/    \
2(0)      2(4)
\
3(5)

Final two steps:

1(1)
/    \
2(0)      2(4)
/   \
5(2)  3(5)
\
6(3)


It preserves the heap property, as we are inserting the nodes in order as children of previously inserted nodes. It preserves the inorder property, as we are using the indexes to position the elements on the tree.

Is there any better solution I am missing? I would like to find a linear one or prove that it cannot exist.

• Inserting in the new tree doesn't have an $O(\log n)$ bound since it's not necessarily of such a height. Consider the sorted array, for instance. – Raphael Jul 23 '17 at 10:23

I think I have found a linear solution. We can build the tree keeping a pointer to its rightmost element. Every time we want to insert a new value, we compare it to the rightmost element:

• if it is smaller, we proceed to compare it to the parent of the current node, ascending through the rightmost branch.
• if it is greater, we append it as its right child, and append the previous right child as the left child of the new node.

As every comparison adds a new element or removes an element from the rightmost branch, we know this is done in ${\cal O}(n)$.

In my example:

1st step

2 <--

2nd step

1 <--
/
2

3rd and 4th steps

1
/ \
2   5
\
6 <--

5th step

1
/ \
2   2 <--
/
5
\
6

6th step

1
/ \
2   2
/ \
5   3
\
6


The second and fifth steps are using the second case of the algorithm, the rest are using the first case.

here is my solution when I met this question during interview:

public TreeNode buildTree(int[] inArray){
if (inArray == null || inArray.length == 0) return null;

int n = inArray.length;
return dfs(inArray, 0, n - 1);
}

private TreeNode dfs(int[] inArray, int start, int end){

if (start == end){
return new TreeNode(inArray[start]);
}

if (start > end){
return null;
}

int minIndex = findMin(inArray, start, end);
TreeNode curNode = new TreeNode(inArray[minIndex]);

TreeNode leftNode = dfs(inArray, start, minIndex - 1);
TreeNode rightNode = dfs(inArray, minIndex + 1, right);

curNode.left = leftNode;

curNode.right = rightNode;

return curNode;
}

private int findMin(int[] inArray, int start, int end){
int minIndex = -1;
int min = Integer.MAX_VALUE;
for (int i = start; i <= end; i++){
if (inArray[i] < min){
minIndex = i;
min = inArray[i];
}
}

return minIndex;
}

• Welcome to Computer Science! Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. – Raphael Jul 23 '17 at 10:24

Just refere wiki: https://en.wikipedia.org/wiki/Binary_heap it a trivial algoritm using sift down operation. But advise you to do in on your own. Should be simple. Why do you need unbalances tree by the way? Should work for unbalances, I think.

• Would that preserve the inorder of the array? – Mario Román Nov 22 '16 at 20:17
• I think I need an unbalanced heap (not a complete balanced one) because I think there is no way to find a complete heap satisfying the inorder property I have asked for in my example. Is there a complete binary heap whose inorder is "2 1 2 3 4"? – Mario Román Nov 22 '16 at 20:21
• I would say it not completed. what diff – PavelOliynyk Nov 22 '16 at 20:33
• My question specifically asks to build a tree with the heap property whose inorder is the original list. Using the standard methods for building binary heaps, in the "2 1 2 3 4" example I arrive at a heap whose inorder is "3 2 4 1 2". I don't see how the standard methods for building binary heaps help me to build a tree whose inorder traversal is equal to the original list. Am I missing something? I have not found this question answered in wikipedia, where they talk only about heaps with the shape property. – Mario Román Nov 22 '16 at 21:29
• I understand the traditional binary complete heaps, max-heaps and min-heaps; I am asking a question about trees with the heap property. – Mario Román Nov 22 '16 at 22:27