# Questions tagged [binary-search-trees]

The tag has no usage guidance.

147 questions
Filter by
Sorted by
Tagged with
46 views

### How does depths of nodes change after left-rotation in a BST (Exercise qustion from Cormen)

Let a,b,c be arbitrary nodes in the subtrees $\alpha$, $\beta$, $\gamma$, respectively, in the left tree of Figure 13.2. How do the depths of a,b,c change when a left rotation is performed on node x ...
• 109
15 views

### How can I get the overall winner's leaf node in a loser tournament tree used for k-way merge?

I've read the wikipedia that has some insight on how a loser tournament tree ought to be constructed, but I'm confused as hell by the pseudo-code shown. How are you supposed to get the overall winner'...
• 113
26 views

### What is the gold-standard description of the 2-3 tree (search, insert, delete)?

After several hours of frustration, I finally realized that the definition of two-three trees aren't standard (my lecture notes, this video, this other video, and Wikipedia) are different. My lecture ...
21 views

### Best Case of Red Black Tree Insertion and Deletion

Question: During the insertion and deletion operation of a Red Black Tree data structure, each operation, can result in $\Omega(\log{n})$ color inversions? True or False? EDIT: Each operation ...
50 views

### Complexity of finding the kth smallest element of all the elements in two order statistics binary search trees

What is the time complexity of finding the kth smallest element of all the elements in two order statistics binary search trees? An order statistics tree is a binary search tree where the size of a ...
70 views

### Solution Verification: How does the postorder traversal of a BST change after rotating left?

Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$. How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the ...
• 164
79 views

### I think I have discovered a new sorting algorithm using binary search tree [closed]

If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
1 vote
29 views

### What is the time complexity of adding to a BST if we are to maintain balance

If we have a BST but want to keep it balanced, how much more expensive does adding an element to it become? Clearly adding an element (without maintaining balance) is of time complexity O(log(n)), as ...
27 views

### Red Black Tree: number of internal nodes vs leaf nodes

Given a generic Red Black Tree with n nodes is correct to say that the number of internal nodes is ⌊n/2⌋ and the number of leaf nodes is ⌊n/2⌋ + 1 ?
• 337
49 views

### Depth-first search (DFS) time complexity for a Red-Black Tree

If we indicate n as the number of nodes of a Red-Black Tree, which is the time complexity of a DFS algorithm that analyzes only the internal nodes of the Tree? I think that the complexity is O(n), but ...
• 337
115 views

### Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order. I believe that I understood the three terms pretty well, and ...
• 187
91 views

49 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 ...
61 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
90 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: ...
• 147
1 vote
488 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, ...
• 113
1 vote
452 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 ...
• 113
1k 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 ...
55 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). ...
• 151
772 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 <...
• 449
1 vote
610 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 ...