# Is this a good way to arrange data in a tree?

I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes.

As binary search trees have numbers greater than the root node on the right and the numbers lesser than the node on the left, we can further divide the tree into odd and even numbers to make the search easier(as we have to just check the last bit to verify if a number is odd or even)

Example:

S = {5,12,14,1,7,2,18,9,11,16,22}

This can be arranged in a tree as follows:

Here, if we have to search for element 9, we just have to look at the left side of the root node which is a BST as 9 is odd, and continue a normal binary search.

Does this make the normal BST any better or is it just unnecessary to divide it on the basis of Odd and Even elements?

• So... basically a LSB radix tree, then? Commented Jun 13, 2021 at 14:02
• i guess radix trees have the complexity of O(n) but i observe this one to have O(lg n).. (please correct me if i am wrong)
– Yuv
Commented Jun 13, 2021 at 15:18
• Good point. How about Patricia tries? Commented Jun 14, 2021 at 5:51
• Yes, I guess thats a good example
– Yuv
Commented Jun 14, 2021 at 8:16

It doesn't significantly increase the speed, the increase will just be a constant at best. Essentially, you still search the same tree, just in a different ordering, and that means you will still do $$O(\log(n))$$ operations to search a number.