# Questions tagged [binary-search-trees]

The tag has no usage guidance.

162 questions
Filter by
Sorted by
Tagged with
38k views

### What is "rank" in a binary search tree and how can it be useful?

I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me. What I have ...
• 245
1k views

### Data structure for handling intervals

I am trying to create a data structure for handling the subsets of the real line of the form $[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: ...
• 101
4k views

### If inorder traversal of a tree is in ascending order will the tree definitely be a BST?

For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?
520 views

### Balanced Binary Search Tree Two-Sum with Constraints

My question spawns from this question. The question is straightforward: Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value? Now ...
• 4,451
3k views

### Why use binary search trees when hash tables exist?

Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log ...
• 581
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 ...
• 225
76 views

### Completeness of red-black tree operations

Red-black trees are defined to have the following invariants: The nodes are in sorted order (it is a binary search tree). The root is black, and leaves are black. Every red node has black children. ...
5k views

### Why is Binary Heap never unbalanced?

My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?...
• 141
670 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 ...
• 43
4k views

### BST representation of Hash Tables

I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables. I googled a lot for BST Representation of Hash Table. Code in C++ but didn't ...
25k views

### Which of the following sequences could not be the sequences of nodes examined in a binary search tree?

Suppose that we have numbers between $1$ and $1000$ in a binary search tree and want to search for the number $363$. Which of the following sequences could not be the sequences of nodes examined <...
679 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 ...
90 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 ...
147 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 ...
• 189
279 views

• 203
561 views

### How to find the number of Binary Search Trees with given number of nodes and leaves?

With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that: Exactly $1$ leaf node(s) present? Exactly $2$ leaf nodes present? I was able to solve the first ...
• 205
91 views

### Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
4k views

### How many permutations for generating a specific binary search tree?

The keys 2, 4, 6, 7, and 8 have been inserted, one by one, in some unknown order, into an initially empty BST. The result is this BST: There are 120 different permutations of the five keys, but not ...
• 131
131 views

### Visualizing How of KD-tree Data Structure Splits Space

I am trying to understand how KD-tree works when we insert a node and how it splits the xy plane, please. Below $[5, 4]$ splits the xy-plane into left and right parts while $[2,6]$ splits it into top ...
• 505
126 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 ...
• 203
2k 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
212 views

### BST - Sufficient condition for connecting a node to a parent

Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree. I want to prove that if I insert a node X into the tree and node X is ...
78 views

### What is the average size of a jump in a binary tree?

Assume that a full binary tree is layed out in memory recursively in the following way. First the Root followed by Tree representation of left subtree followed by tree representation of right subtree. ...
• 118
136 views

### Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 . $n$ : number of nodes in the tree $Z_{n,k}$ : Indicator random variable that activates when rank of the root ...
1k views

### Binary Search Tree Stability Data Structure

After constructing a binary search tree, you can read off the key values in ascending order by performing an in-order traversal. Will the resulting sorted order be stable? If so, how would the tree ...
• 121
230 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 ...
• 129
885 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 ...
1k 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 ...
• 121
67 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 ...
• 141
356 views

### How many similar binary search trees are made from different permutations?

If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would ...
120 views

### What would be the probabilty of a randomly generated tree to be a Red-Black Tree

The question is not related to the homework I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
1k views

### Why is the number of comparisons in a BST missing key lookup about 2 ln N?

In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1....
1 vote
440 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 ...
• 151
1 vote
622 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 ...
1 vote
52 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: ...
1 vote
369 views

### how does rotation works in AVL trees and what is a good way to understand it?

If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 ...
1 vote
757 views

### Why do we use multiple data structures? [duplicate]

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees. Both runs in worst case O(n) in the same operations, so why don't we use only ...
• 133
1 vote
2k 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 ...
1 vote
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 ...