CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
Rizvan
Rizvan

Reputation: 2355

Binary Search Tree Multiply nodes by -1

Consider you have Binary Search Tree, in case multiply all nodes by -1 then can anybody please let me know if its still a Binary Search Tree?

Whether is it possible to write a function which converts it back to Binary Search Tree ?

Upvotes: 1

Views: 588

Answers (2)

Andrew Shepherd
Andrew Shepherd

Reputation: 45262

Interesting problem.

In a Binary Search Tree, the structure of object graph indicates the sort ordering.

By multiplying all of the object by -1, it's now reverse sorted.

EG:

3 4 8 9 12

becomes

-3 -4 -8 -9 -12

So, how do you make this still maintain the Binary Search Tree property?

A binary tree would consist of two things: a graph of object nodes, and the knowledge on how to compare the objects. The comparison function would look something like this:

 Compare(left, right) {
     return (left < right);
 }

If you perform a transformation on the values inside your binary tree, you can change its comparison function and then it will continue to behave as it should.

 myBinaryTree.comparisonFunction = function(left, right) { return (right < left) };

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373042

In a binary search tree, all elements of a node's left subtree must be less than (or equal to, in some trees) the node and all elements of a node's right subtree must be greater than (or equal to, in some trees) the node. If you multiply all the nodes by -1, you end up flipping this so that the left subtree of each node stores the greater values and the right subtree stores the lesser values. To convert this back into a BST, you'd have to "flip" the BST by mirroring it. I'll leave the details of how to do that as an exercise; it's a classic CS problem with a beautiful recursive solution.

Hope this helps!

Upvotes: 1

Related Questions