As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [binary-search-trees]

The tag has no usage guidance.

156 questions
Filter by
Sorted by
Tagged with
1 vote
24 views

### Merge K BST of N elements in total into a single RBT in O(N log K) time

I have the following question to solve; Given $K$ BST consisting of $N$ total elements, show how you can create a Red Black Tree in $O(N\log K)$ time. I had the following idea but it falls on the ...
63 views

### Deletion of a node from a BST

Placed exactly the code and the explanation of the book : Introduction to Algorithms Third Edition In order to move subtrees around within the binary search tree, we define a subroutine TRANSPLANT, ...
1 vote
57 views

### Merge two binary search trees

Consider two binary search trees T1 and T2, each with height h, with all values in T1 less than all values in T2. I want to merge these both trees to get a new binary search tree of height at most h+1 ...
24 views

### How many times is a node rotated towards the root in a weight-balanced tree?

In this paper they prove that the number of rotations after doing $n$ insertions or deletions to a weight-balanced tree is $O(n)$ (when starting from an empty tree). What isn't clear to me though is ...
196 views

### Binary Search Tree Updating

How can I update values in Binary Search Tree without affecting its properties (all the nodes in the left subtree have values that are less than the value of the root node and all the nodes of the ...
1 vote
70 views

### Two statements about optimal binary search trees

This is a paragraph from the book CLRS: What we need is known as an optimal binary search tree. Formally, we are given a sequence $K = (k_1, k_2, ..., k_n)$ of $n$ distinct keys in sorted order (so ...
1 vote
67 views

### What is the minimal number of nodes with the right subtree in a height-balanced BST?

I have a binary search tree of size $N$. The tree is height balanced: difference of heights of a node's subtrees is no more than 1 (true for RB or AVL trees). $K$ is the number of nodes that have a ...
1 vote
79 views

### Randomly generated binary search trees case comparison

Although not an assignment, just out of curiosity; I am trying to compare a two cases A scenario where I pick a tree out of the set of possible binary search trees on the keys $1,2,\ldots,n$, with ...
37 views

### What binary search tree to use if probabilities of element query are known apriori?

There is a universal set of integer pairs $(key; outcomes)$, a subset of which is inserted into a binary search tree in $O(\log n)$ time for each key and can be searched by keys. Afterwards a large ...
19 views

### How to find number of nodes less than K in a BST in log(h) time WITHOUT recursion? [duplicate]

I understand the recursive procedure after seeing a similar question in stackexchange but our professor requires us to not use recursion.
143 views

### Is there a way to parallelise find and inserts for a binary search tree?

Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism. I have implemented a ...
128 views

### Did I invent a new data structure?

I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since ...
111 views

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

Let a,b,c be arbitrary nodes in the subtrees $\alpha$, $\beta$, $\gamma$, respectively, in the left tree of Figure 13.2 (that is given below). How do the depths of a,b,c change when a left rotation is ...
23 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'...
29 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 ...
65 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 ...
96 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 ...
85 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
368 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 ...
37 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 ?
112 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 ...
125 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 ...
200 views

A priority search tree is a binary tree satisfying the following: every node $u$ stores a point $p_u = (x_u,y_u)$ every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate. If $... 0 votes 1 answer 72 views ### BST subtree value range Suppose we have a node x in BST, and let max and min be the largest and smallest keys in the subtree rooted at x respectively. Prove that for any node n outside this subtree, the key of n is either ... 4 votes 1 answer 552 views ### Big O vs. Big Theta for AVL tree operations On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ... 0 votes 1 answer 45 views ### n search operations on an arbitrary Splay tree For an arbitrary spay tree with n nodes, if we perform n find operations, is there a way of generalizing what the tree would ... 1 vote 1 answer 73 views ### Least-balanced possible red-black tree of n distinct nodes Let's say we have a red-black tree of$n$total nodes where all keys are distinct. The subtree rooted at the root node's left child has$n_L$nodes, and similarly the subtree rooted at the root node'... 0 votes 1 answer 24 views ### Which particular data structure should I use if I want a persistent balanced search tree? As title, I'm trying to implement a text editor with the rope data structure, which is backed by binary search tree. Since I want it to have persistent undos, the underlaying data structure should ... 0 votes 1 answer 71 views ### What's the sum of heights of a random binary search tree What's the sum of heights of a random binary search tree? By a random binary search tree, I mean the usual definition: you have$n$keys to be inserted, and all Permutations are equally likely. The ... 1 vote 1 answer 183 views ### Interval Tree by Augmenting an AVL Tree According to Wikipedia: An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. ... 0 votes 1 answer 294 views ### Height of AVL Tree I found an AVL tree implementation on the internet and experimented: For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24. While these heights are lg(n)-ish, I am ... 0 votes 0 answers 23 views ### Two variants of the BST remove algorithm I have seen two variants of the BST remove algorithm in the case where the node to be removed has both children. Variant 1: Replace the node with the right-most child in the left subtree Variant 2: ... 1 vote 3 answers 389 views ### How does the Inorder-tree-walk algorithm move to a different node after hitting a leaf? A friend and I did the Inorder-tree-walk with pen and paper. We both can't figure out how the algorithm would move 'up' the tree again upon hitting a leaf: We are using the algorithm as described by ... 2 votes 1 answer 114 views ### How to join two Scapegoat Trees in O(log n) time? I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees$L$and$R$are joined to create a single ... 0 votes 0 answers 85 views ### Rebalance the following AVL tree after inserting G. You need to show the middle step if it happens. Briefly explain the operations I recently learned AVL Trees but I still lack a complete understanding of the concept. I understand that an AVL tree is a Binary search tree that checks for the height of the tree, but I still don't ... 1 vote 3 answers 1k 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 ... 3 votes 1 answer 73 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 1 answer 64 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 1 answer 383 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 1 answer 69 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 0 answers 70 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 1 answer 61 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 1 answer 283 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 0 answers 76 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 0 answers 96 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 ... 1 vote 1 answer 599 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 ... 1 vote 1 answer 64 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 vote 1 answer 180 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$... 1 vote
62 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 ... 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)$ ... 