java - Efficient algorithm for finding the in-order rank of a binary tree node -

-

given binary tree (not binary search tree) , node in tree, efficient algorithm (in java preferably) find in-order rank of node?

an o(n) algorithm possible traversal (either recursive or iterative). there better one? suggestion.

imagine worst case: each node has 1 left child, whole tree becomes linked list.

if given root, calculate rank need access leaf, in case costs o(n). o(n) in worst case best can achieve without storing additional information in nodes.


Comments

Post a Comment

Popular posts from this blog

html - Firefox flex bug applied to buttons? -

-
i'm trying apply flex button on firefox i'm having problem on chrome doesn't happens. this css: .button { display: inline-flex; align-items: center; } as can see in fiddle, "caret" word moved new line, happens if element <button> tag, <div> works expected. http://codepen.io/anon/pen/xblmgx is firefox bug or there css i'm missing? nevermind, looks "mr firefox" doesn't idea... <button> not implementable (by browsers) in pure css, bit of black box, perspective of css. means don't react in same way e.g. <div> would. this isn't specific flexbox -- e.g. don't render scrollbars if put "overflow:scroll" on button, , don't render table if put "display:table" on it. stepping further, isn't specific <button> . consider <fieldset> , <table> have special rendering behavior: data:text/html,<fieldset style="d...
Read more

html - Missing border-right in select on Firefox -

-
Image
when put select div width , padding-left, options have no border on right. more, happend if select have width 118px , parent have 15px of padding left! have idea, going on? my code: <!doctype html> <html> <head lang="en"> </head> <body> <div style="width: 1000px; padding-left: 15px;"> <select style="width: 118px;"> <option>a</option> <option>b</option> <option>c</option> </select> </div> </body> </html> and result: here plunker: click it happend on firefox on windows. tested on 40.0.2 version -webkit-box-sizing: border-box; -moz-box-sizing: border-box; -ms-box-sizing: border-box; box-sizing: border-box; source: https://stackoverflow.com/a/11390432/4431269 source of problem: https://bugzilla.mozilla.org/show_bug.cgi?id=924068 and use of google ! edit: (source of problem, explained) after rea...
Read more

python - build a suggestions list using fuzzywuzzy -

-
i building suggestion engine database. i'm using fuzzywuzzy module match user input string existing database shown below. if request.method == "get": display_dict = {} user_input = request.get["user_input"] # user input match_dict = {} food_items_obj = food_items.objects.all() # fetch objects table items in food_items_obj : match = fuzz.ratio(user_input.lower(),items.name.lower()) # try match user input existing names match_dict[match] = items.name # put 1 dictionary matched_dict = ordereddict(sorted(match_dict.items(),reverse = true)) # sort dictionary if max(matched_dict.keys()) == 100: # if exact match put in dict , return display_dict[100] = matched_dict[100] else : # if not found try best matching words.. ###########this part need help! ############# k,v in matched_dict.items(): if user_input in v : display_dict[k]...
Read more