Contructing a special tree, from numerical sequence

user_12355768 0
Viewed 57

I have an interesting task, but I have no clue how to solve it.

The minim binary tree M(a) for a given sequence a= (a1, . . . , an) without repeated elements is defined as follows: Be ai the minimal number of (a1, . . . , an), and then the root of M(a) is ai, its left subtree is M(a1, . . . , ai-1) and its right subtree is M(ai+1, . . . . , an). M(∅) is a empty tree. For a given sequence, construct a minimum tree in O(n). Notice that subtrees are also M so they have to follow the rules.

Example Example here. Thx for help.

binary-tree theory graph
2 Answers
user_123557680 
C:\Users\James\code\minbin>minbin
1 -> 2
2 -> 3
3 -> 7
3 -> 5
5 -> 11
5 -> 8
8 -> 15
8 -> 19
1 -> 12
12 -> 13

You can see the code that produces this output at https://gist.github.com/JamesBremner/ac9ad8db15eafaad57a89532e64ff7bf

The algorithm is recursive:

  • find smallest element
  • link parent to smallest
  • split remaining numbers
  • if left is single, link from smallest, else call split again
  • if right is single, link from smallest, else call split again
  • return
user_165820
Related