algorithm - Get interval of binary search tree as fast as sorted array -

currently implementing bst in java university project. know, bst quite in searching single unit o(log n) in balanced tree.

but how perform search between value a , b? (a < b)

let's have tree

│               ┌── 125 │           ┌── 122 │           │   └── 120 │       ┌── 117 │       │   │   ┌── 113 │       │   └── 112 │       │       └── 108 │   ┌── 86 │   │   │   ┌── 85 │   │   └── 72 └── 59     │           ┌── 56     │       ┌── 52     │   ┌── 47     │   │   │   ┌── 43     │   │   └── 39     │   │       │   ┌── 38     │   │       └── 36     └── 28         │       ┌── 18         │   ┌── 15         └── 2             └── 1 

i want create method range(a,b) return value between a , b inclusive. (note: a , b not necessary in tree!)

for example: range(53,112) return 56,59,72,85,86,108,112

here pseudo code

/* recursive method */ range(a,b)     range(a,b,root);  /* helper method */ range(a,b,node)     if (a <= node.value <= b)         if (node.left != null) , (node.value != a)             range(a,b,node.left)          print node.value          if (node.right != null) , (node.value != b)             range(a,b,node.right)      else if node.value <         if (node.right != null)             range(a,b,node.right)      else // node.value > b         if (node.left != null)             range(a,b,node.left) 

but think method slower.

for example, in sorted array, have perform binary search on a , b , respective index. after that, iterate index of a index of b.

is true bst perform slower on searching multiple values? possible improve algorithm fast sorted array?

depending on how can return result, sorted array may have huge advantage of not needing copy results anywhere. returning pointer+length view array far faster , more cache-friendly making copy of range buffer. tree has copy elements out of tree. if need copy (to modify or whatever), memcpy much faster walking tree.

this isn't issue if can process on fly while walking tree (like you're doing print).

i seem write answers before googling. turns out trees answer range queries thing. apparently it's done 2d or 3d ranges (where each point has x , y coordinates, example), can't sorted array. assume because though it's efficient possible, it's not efficient returning pointer+length window sorted array!

i'm not going copy/paste whole algorithm wikipedia, clever idea:

to report points lie in interval [x1, x2], start searching x1 , x2. @ vertex in tree, search paths x1 , x2 diverge

this how efficiently detect whole subtrees know in range, see wikipedia and/or google "tree range query" lots of details.

---

my pre-googling observation avoid comparisons , walk subtrees. in example, left subtree of 86 guaranteed in range, because know they're >59 , <86, tighter bound [a..b]. hadn't thought of way special case wouldn't maybe cost more overhead saved.