tree - GIven a level order FInd BST -

-

given bst level-order traversal is:

99 65 53 80 22 62 98 21 49 82 36 51

what tree if make tree following level order traversal?

here's how arrived @ bst present @ bottom.

the main governing rule 1 has apply bst: if "order" elements, every node in left subtree of node has considered "before" node, , every node in right subtree has considered "after" node.

since list numbers, , nothing more rules ordering, numerical ordering assumed.

as such, when placing nodes have find correct location of each node given following procedure:

  1. decide if can find place on current level (if there room more nodes there). find find places place if didn't care bst rule. check each such position see if legal position. there should one.
  2. if find such place, place there, if not, go next level , place in leftmost legal position there.
  3. when placing more nodes on existing level, go left right.

so here's runthrough of given numbers:

  1. the first level contains 1 number, 99.
  2. the second level can contain 1 or 2 numbers, 65 has here perhaps 53 not. since 65 less 99 has placed down-left 99. can 53 placed down-right 99? no, has on third level.
  3. so 53 on third level, , has down-left 65.
  4. what 80? either on third level, down-right 65, or on fourth line. can on fourth line? either have less 53, or greater 53 , smaller 65. greater 65 cannot on fourth level has on third, down-right 65.
  5. next comes 22, , less 65, since we're starting level 4 easy place, has placed down-right 53.
  6. next up, 62, since still within range of level above can have under it, have find right place it. since greater 53, not greater 65, has placed down-right 53.
  7. 98 greater 80. since still less 99, still has place in main left subtree of 99 place down-right 80.
  8. 21 down-left 22.
  9. 49 less 53, greater 22, placed down-right 22.
  10. 82 has either placed down-left or down-right 62, down-left or down-right 98, or start new line. legal position in line down-left 98.
  11. 36 greater 21, not greater 49, has placed either down-right 21 or down-left 49. since 36 greater 22, has down-left 49.
  12. the final number 51 greater 51, not greater 53, has placed somewhere in left subtree of 53, , place down-right 49.

final bst:

            99            /          65         /  \       53    80      /  \     \    22    62    98   /  \        / 21    49    82      /  \    36    51

Comments

Post a Comment

Popular posts from this blog

javascript - Chart.js (Radar Chart) different scaleLineColor for each scaleLine -

-
Image
i try , create radar chart using chart.js has various colours each scaleline, or coloured between scalelines. wondering if possible? from: to: i have working graph, though there doesn't seem method change individual scale lines. kind regards leigh you can extend radar chart type this, so chart.types.radar.extend({ name: "radaralt", initialize: function (data) { chart.types.radar.prototype.initialize.apply(this, arguments); var originalscaledraw = this.scale.draw; var ctx = this.chart.ctx; this.scale.draw = function () { var linewidth = this.linewidth; // bypasses line drawing in originalscaledraw this.linewidth = linewidth; originalscaledraw.apply(this, arguments); ctx.linewidth = this.linewidth; var scale = this; // draw chart.helpers.each(scale.ylabels, function (label, index) { // color of ...
Read more

apache - Error with PHP mail(): Multiple or malformed newlines found in additional_header -

-
suddenly have started receiving above error without changes having been made script. host 1and1 (i know...) the script still works fine on different server, , suspicion there must have been server config change has lead this, although hosts plead ignorance. there's no information on above error @ in google can find - have ideas? server running apache if helps. had similar problem. came out of blue. no php code changed. what changed: php upgraded 5.5.25-1 5.5.26. a security risk in php mail() function has been fixed , newlines in additional_headers allowed no more. because newlines mean: starts email message (and surely don't want inject newlines through headers followed evil message). what have worked fine, e.g. having newlines after headers or passing whole message additional_headers , function no more. solution : sanitize headers. no multiple newlines in additional_headers argument. these count "multiple or malformed newlines":...
Read more

java - Android – MapFragment overlay button shadow, just like MyLocation button -

-
Image
i'm struggling add shadow custom overlay button on google map. goal make custom button google's mylocation button. here's how app looks now: layout.xml <relativelayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" xmlns:map="http://schemas.android.com/apk/res-auto" android:layout_height="match_parent" android:layout_width="match_parent" style="@style/apptheme"> <fragment android:layout_width="match_parent" android:layout_height="match_parent" android:id="@+id/map" tools:context=".mapsactivity" android:name="com.google.android.gms.maps.supportmapfragment" android:layout_alignparentend="true" android:layout_alignparentstart="true" android:layout_alignparentbottom="true" ...
Read more