how can you build binary tree without sorting it, I.E
if i have a input 5 4 9 8 1 2 7 how can you insert that into a reference based binary tree. I know this can be easily implemented with Array, but is it possible with reference base?
1
-
Nope its just some extra work that we can do to sharpen our skillsRaju Kumar– Raju Kumar2012-02-07 03:03:38 +00:00Commented Feb 7, 2012 at 3:03
Add a comment
|
2 Answers
Tree buildTree(int[] array, int index) {
if(index > array.length) { return null; }
return new Tree(
array[index],
buildTree(array, 2 * index + 1),
buildTree(array, 2 * index + 2));
}
Most of the work is in the recursion and in the indexing, but it's not too bad at all.
Comments
One simple rule is to always insert into the left subtree and then switch the subtrees. The right subtree will always be 0-1 elements larger than the left subtree, so you can always insert into the left subtree. Now, the left subtree is 0-1 elements larger than the right subtree, so you want to switch the subtrees to preserve the invariant. In pseudocode:
insert(t,v) {
if (t == null) {
return new TreeNode(v,null,null)
} else {
left = insert(t.left,v)
right = t.right
t.left = right
t.right = left
return t
}
}
4 Comments
templatetypedef
This builds a sorted tree, something the OP explicitly asked not to do.
Retief
I read that as build a tree (that I assumed was sorted) from unsorted input. Fixed.
templatetypedef
@Retief- Your answer is still pretty vague about how specifically to accomplish this, and I don't think it can be built into a working answer without significant effort. If you can improve your answer to detail exactly how you'd build the tree, then I'll remove my downvote.
Retief
@templatetypedef Better? I am omitting iterating across the list, inserting each one into the tree so far, but that is not a complex or hard to write function.