CODEWITHSUNDEEP
javatreebinary-tree
Raju Kumar
Raju Kumar

Reputation: 1265

Insert into binary tree without sorting input

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?

Upvotes: 0

Views: 1105

Answers (2)

Retief
Retief

Reputation: 3217

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
    }
}

Upvotes: 2

Louis Wasserman
Louis Wasserman

Reputation: 198023

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.

Upvotes: 3

Related Questions