All Questions
Tagged with binary-search-trees data-structures
56 questions
4
votes
3
answers
707
views
What purpose do the leaves in a range trees serve?
I'm getting into algorithms and I came upon range trees. What confuses me is the leaves in a range tree, since for example:
When you remove the leaves:
It's just a regular BST.
And, every ...
5
votes
1
answer
1k
views
What is the advantage of leaf trees vs. node trees?
In the book "Advanced Data Structures", Chapter 2 ("Search Trees"), the author, Peter Braß, mentions two versions of binary trees (emphases in the quoted text are mine):
"...two different models ...
0
votes
1
answer
419
views
What happens internally when you remove an object from a treemap
I am wondering what happens if you remove an object in the middle of a treemap.
If the treemap would look something like this:
So what would happen if you remove the number 30? Because 27 and 34 ...
-3
votes
1
answer
9k
views
Constructing binary search tree from given data
The data are in alphabets.
U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A.
Perform pre, in and post order traversals.
I'm confused as how to construct it in the 1st place. Only sense i ...
0
votes
0
answers
70
views
Find keys between $x$ and $y$ in binary search tree
Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
3
votes
1
answer
756
views
Binary Search Tree Traversal output validity and unique BST construction
I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals :
Given x-order traversal output of BST, can we state if it is valid or invalid output?
(For ...