algorithm - The Great Tree list recursion program -

-

i faced interesting problem called great tree-list problem. problem follows :

in ordered binary tree, each node contains single data element , "small" , "large" pointers sub-trees .all nodes in "small" sub-tree less or equal data in parent node. nodes in "large" sub-tree greater parent node. , circular doubly linked list consist of previous , next pointers.

the problem take ordered binary tree , rearrange internal pointers make circular doubly linked list out of it. "small" pointer should play role of "previous" , "large" pointer should play role of "next". list should arranged nodes in increasing order. have write recursive function & return head pointer new list.

the operation should done in o(n) time.

i understand recursion go down tree, how recursively change small , large sub-trees lists, have append lists parent node.

how should approach problem?.. need direction solve problem!.

the idea create method converts tree node containing subtrees (children nodes) loop. , given node has converted children (e.g. after recursive calls came back), create new loop pointing large pointer (next) of largest node smallest node, , small pointer of smallest node largest node.

may not complete, close this:

tree_node {     small     large }  convert(node){     //base case 1, if leaf node     if node.small == null && node.large == null         return (self, self)      //recursively convert children     if node.small !=null         smallest, larger = convert(node.small)     else         smallest = larger = self      if node.large !=null         smaller, largest = convert(node.large)     else         smaller = largest = self      //wrap ends of chain     largest.large = smallest     smallest.small = largest     //wrap mid part     smaller.small = larger     larger.large = small      //return pointers absolute smallest , largest of subtree     return (smallest, largest) }  //actually doing  convert(tree.root)

Comments

Post a Comment

Popular posts from this blog

Django REST Framework perform_create: You cannot call `.save()` after accessing `serializer.data` -

-
i have following viewset: class artistprofileviewset(viewsets.modelviewset): queryset = artistprofile.objects.all() serializer_class = artistprofileserializer def perform_create(self, serializer): if serializer.is_valid(): serializer.save() with following serializers: class simpleartisttrackserializer(serializers.hyperlinkedmodelserializer): class meta: model = artisttrack fields = (...my fields...) class artistprofileserializer(serializers.hyperlinkedmodelserializer): owners = userserializer(many=true, required=false) tracks = simpleartisttrackserializer(many=true, required=false) class meta: model = artistprofile fields = (...my fields...) i getting following error: assertionerror: cannot call `.save()` after accessing `serializer.data`.if need access data before committing database inspect 'serializer.validated_data' instead. i don't see editing serializer.data object. th...
Read more

Why does Go error when trying to marshal this JSON? -

-
i'm trying rather simple example of trying decode json file structs using golang. however, when attempting error that json: cannot unmarshal object go value of type []main.track which don't understand. here's code in question, , json can found here . package main import ( "encoding/json" "fmt" "net/http" "os" ) // tracks group of track types type tracks struct { tracks []track } // track represents singular track type track struct { name string url string artist artist } // artist represents single artist type artist struct { name string mbid string url string } func main() { url := "http://ws.audioscrobbler.com/2.0/?method=geo.gettoptracks&api_key=c1572082105bd40d247836b5c1819623&format=json&country=netherlands" response, err := http.get(url) if err != nil { fmt.printf("%s\n", err) os.exit(1) } de...
Read more