Questions tagged [binary-search-trees]
The binary-search-trees tag has no usage guidance.
125
questions
0
votes
0answers
9 views
The number of ways of insertion in binary search tree
The number of ways in which the numbers $1,2,3,4,5,6,7$ can be inserted in an empty binary search tree, such that the resulting tree has height 5, is _________.
Note: The height of a tree with a ...
0
votes
0answers
32 views
How to trasnform search tree into AVL tree with constant memory and in linear time?
How to transform search tree into AVL tree with constant memory and in linear time ?
3
votes
1answer
46 views
Observations about the structure of an optimal Binary Search Tree
My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees.
I am confused about the following sentences:
Consider any subtree of a binary search tree. It must contain ...
1
vote
1answer
40 views
Minimum absolute difference in a BST is always between
Given a Binary Search Tree(BST) I would like to understand can absolute minimum difference between any two nodes of a BST is always between adjacent nodes. If Yes or No can we generalize it ? Assume ...
0
votes
1answer
26 views
When can a (max) heap be a BST?
Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below:
A heap can never be a BST
A heap is ...
0
votes
1answer
22 views
Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time
We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time.
We can do this in linear time but with extra ...
0
votes
0answers
34 views
Calculating the expected height of a randomly built binary search tree
I need to calculate the expected height of a randomly built binary search tree, BST, with 4 different keys: $x < y < z < w$
According to Catalan numbers, there are 14 possible trees, 8 with ...
0
votes
1answer
34 views
Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$
I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key[x] + key[y] = 2 \cdot key[p(x, y)]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$...
1
vote
1answer
49 views
Splay Tree, repeatedly searching for the same key that´s not in the Tree
In a Splay Tree, doing $m$ sequential search operations for the same key that is in the tree has a time complexity in $O(n+m)$ where n is the number of nodes in the Tree. Since the first search has a ...
0
votes
0answers
21 views
BST deletion of node with 2 children by copying right child to predecessor
I try to delete a node, $z$, with 2 children in binary search tree by exchanging $z$'s right child and $z$'s predecessor, $y$, right child, which is NULL because $y$ has no right child, if it had then ...
0
votes
0answers
75 views
Suggest a Data Structure that support the following operations with time complexity O(log(n))
I’m looking for a data structure that supports that store the salaries of it’s employees.
Insert(e) – Insert employee e into the data structure.
AvgDecile(k) – Returns the average salary of the k’th ...
0
votes
0answers
41 views
Average depth BST upper bound
I have a question regarding the BST average depth upper bound. Following the proof from Data Strucutures and Algorithms in Java by Weiss (3rd edition), I was wondering if there was some kind of ...
1
vote
1answer
33 views
For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?
I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
0
votes
1answer
23 views
Converting Binary Search Tree into Decreasing Ordered Linked List
Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the ...
1
vote
1answer
50 views
If a key in a red-black tree has exactly one child (which isn't null) then it is always red
I have the following claim:
Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.
My attempt:
Disproof.
We will exhibit a counterexample:
...
-1
votes
1answer
40 views
Are there any trees where Preorder$(T_1) =$ Preorder$(T_2)$ and Inorder $(T_1) = $Inorder $(T_2)$, but $T_1 \neq T_2$?
Is it possible for two binary trees $T_1 \neq T_2$ that both Preorder and Inorder traversal are equal ?
1
vote
1answer
109 views
Prove a statement about searching in binary search tree
Suppose search $n$ times in a given binary search tree $T$ with $n$ nodes. each searching have cost $C_i$, and $\sum_{i=1}^{n}C_i=O(n\log n)$. Now the problem is to find height of $T$. I think it be $...
0
votes
0answers
43 views
Finding height of binary search tree
Suppose given a binary search tree $T$ with $n$ nodes with depth $h$.
We did $n$ times search with cost $c_i$ for search $i^{th}$ search on
$T$ ,and $\sum_{i=1}^{n}c_i=O(n\log n)$. what we can say ...
0
votes
1answer
47 views
Check two balanced binary search trees that sub set of each other
Given two balanced binary search trees $T_1,T_2$. We want to check,
are $T_1\subseteq T_1$ or not. $T_1$ have $n_1$ nodes, and $T_2$ have
$n_2$ nodes.
Instructor say it can be done in $O(n_1+n_2)$ ...
1
vote
1answer
68 views
Cormen problem 13-1 part d
I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution:
...
0
votes
1answer
176 views
prove correctness of in-order tree traversal subroutine
I'm trying to prove that in-order tree traversal prints the keys in sorted order. it's shown here, but what I want is to prove correctness using ordinary induction.
Claim: For any n-node subtree, ...
1
vote
2answers
363 views
is it possible to create an avl tree given any set of numbers?
I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement?
Let $A$ be ...
0
votes
1answer
470 views
Find amount of elements greater then number k in a BST
I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K.
I found it problematic as there are elements which might be greater then K but wont ...
0
votes
0answers
24 views
Probability that BST has exact height
Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$.
(We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).
...
1
vote
1answer
530 views
What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?
I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <...
1
vote
1answer
231 views
Recurrence formula for optimal binary search tree
This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $.
For ...
4
votes
0answers
66 views
Understanding the Transition points of a BST
I'm trying to understand the definition of Transition point of a BST, as given in Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251
...
1
vote
1answer
41 views
What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?
I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an ...
1
vote
0answers
26 views
Splay tree amortized analysis cost using Access Lemma
Currently studying for an algorithms exam and I came across this question and solution, but I can't understand the solution where it references nodes of depth less than $4\log n$ and not restructuring....
0
votes
2answers
40 views
Call stack is hard to maintain in my brain. What should I?
When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and ...
0
votes
1answer
15 views
Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time
I wonder what is the best data structure I can use in order to achieve the following:
Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ ...
0
votes
1answer
51 views
How many different (full/complete) in-order binary-trees do exist?
Given be a binary tree whose elements printed in-order results in [1,2,3,4].
Q1: How many different binary-trees do exist?
Q2: How many different complete binary-...
0
votes
0answers
14 views
Parent Node in BST
Is it a good idea to store a pointer to the parent node in a binary search rather than to find the parent node several times?
...
0
votes
1answer
272 views
Remove range of keys from Binary Search Tree in O(s+h)
I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h)
where s is the number of keys to remove and h is the height of the tree.
Attempted ...
1
vote
0answers
552 views
Algorithm to delete BST nodes with duplicated values
In a binary search tree the following must hold:
Greater keys are in the right-subtree
Smaller or EQUAL keys belong to the left-subtree
All the algorithms I found to delete a node start by finding ...
0
votes
1answer
813 views
How to find time complexity of this pseudocode
Recently, I came across a question about finding sum of all values in range $[low, high]$ in BST $T$.
Then I formulated following algorithm to carry out that task:
We do inorder traversal of ...
1
vote
2answers
45 views
Inorder tree tranversal on binary search tree doesn't give the elements in order?
I have been told that inorder tree tranversal of binary search trees returns the tree elements in order. I came up with this binary search tree:
...
2
votes
0answers
47 views
Reasoning for awkward style of TreeMap.getHigherEntry
Consider a binary search tree (AVL, red-black, whatever). The goal "find the least key strictly greater than the specified one" ("upper_bound" in C++ STL, higherEntry//higherKey in Java, etc.) can be ...
0
votes
1answer
525 views
Constructing preorder traversal from postorder of a Binary Search Tree in O(n)
We are given postorder traversal of a Binary "SEARCH" Tree (in an array) and we want to find (print) its preorder traversal.
A very naive solution is to check from end until we find element less than ...
1
vote
1answer
47 views
question about the construction of BSTs using a repeated sequence of rotations
How can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1).
0
votes
1answer
51 views
How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural)
How do I construct a perfect BST from an unbalanced BST with $n$ elements (assuming that $n=2^i-1$, $i$ is natural). ** At the worst case of $O(n)$**.
2
votes
1answer
115 views
Height of epsilon-balanced binary search tree
In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:
For example, one can say, a BST is balanced, if each subtree has at
most epsilon * n nodes, ...
0
votes
2answers
457 views
Leaf nodes of B+ Tree
I have a b+ tree and i want to find the record associated with a specific key Ki.
So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
0
votes
2answers
63 views
creating a binary search tree (manual)
I've been given the following values to add to a binary search tree (in the order given)
56, 35, 55, 58, 29, 15, 16, 5, 71, 92, 69, 95
and this is what my tree ended up like:
but apparently it's ...
-1
votes
2answers
33 views
post order for binary search tree
I got this as the post order sequence but the answer says it is wrong. I do get a bit confused with the post order logic as well.
8 11 10 9 13 16 18 15
2
votes
1answer
38 views
in order of binary search tree
This is what I got for the in-order of the bst but it's wrong because I'm answering some questions about some successors of some of the letters and I got them wrong. so I'm wondering where in this in-...
0
votes
1answer
1k views
How is the right, root, left order traversal called in a binary search tree?
In a Binary Search Tree you have the following orders for traversal:
Left, Root, Right is called Inorder (or ascending order).
Root, Left, Right is called Preorder.
Left, Right, Root is called ...
1
vote
2answers
3k views
Time complexity for balancing an unbalanced binary tree
The question here is that: There is an unbalanced binary tree with n-nodes. What is the time complexity to balance the tree?
The solution I thought of involved solving using Recursion where for the ...
0
votes
1answer
174 views
Is the tree shown a valid red-black tree?
I have made a red-black tree and I think that it is not valid. Could someone please verify?
As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes ...
0
votes
0answers
35 views
RB trees from any balanced BST?
Given any perfectly balanced binary search tree, is it always possible to assign a coloring to the nodes so that it becomes a Red-Black tree? If so, how do you prove this, and if false, what would be ...
