Questions tagged [binary-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10 votes
4 answers
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 ...
JustBlossom's user avatar
10 votes
1 answer
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: ...
kissanpentu's user avatar
7 votes
3 answers
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?
Lavlesh Mishra's user avatar
6 votes
2 answers
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 ...
ryan's user avatar
  • 4,451
5 votes
4 answers
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 ...
wsaleem's user avatar
  • 581
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 ...
Aky's user avatar
  • 225
5 votes
0 answers
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. ...
Mario Carneiro's user avatar
4 votes
3 answers
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?...
Hang Nguyen's user avatar
4 votes
1 answer
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 ...
573hgkaf's user avatar
4 votes
1 answer
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 ...
abhimanyuaryan's user avatar
4 votes
2 answers
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 <...
Squanchinator's user avatar
4 votes
3 answers
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 ...
Mr. Bombastic's user avatar
4 votes
0 answers
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 ...
Margaret Bloom's user avatar
3 votes
1 answer
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 ...
Rodrigo's user avatar
  • 189
3 votes
1 answer
279 views

finding an algorithm for creating a priority search tree in linear time with presorting

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 $...
user3472's user avatar
  • 207
3 votes
1 answer
86 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 ...
user8171079's user avatar
3 votes
1 answer
6k views

Average height of a BST with n Nodes

I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My ...
zSkeeter135's user avatar
3 votes
1 answer
594 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 ...
Mahesha999's user avatar
  • 1,745
3 votes
0 answers
52 views

If I randomly swap pairs of inputs how unbalanced will a binary search tree become?

Treesort sorts input by putting input into a binary search tree and then flattening the tree. In some cases the tree can become unbalanced and so a self-balancing tree is required. There is no ...
Molly Stewart-Gallus's user avatar
2 votes
1 answer
152 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, ...
pete's user avatar
  • 143
2 votes
1 answer
50 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-...
Holz's user avatar
  • 21
2 votes
1 answer
2k views

Should all internal node keys in B+ tree also be in the leaves?

I was reading about B+ tree insertion. The algorithm takes following form: Insert the new node as the leaf node. If the leaf node overflows, split the node and copy the middle element to the parent ...
Mahesha999's user avatar
  • 1,745
2 votes
1 answer
4k views

Facts about internal and external path lengths of binary tree

While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some ...
Mahesha999's user avatar
  • 1,745
2 votes
1 answer
119 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 ...
Pwaol's user avatar
  • 164
2 votes
1 answer
416 views

Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes

I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{...
rtheunissen's user avatar
2 votes
1 answer
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 ...
Aditya's user avatar
  • 205
2 votes
1 answer
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 ...
Dr Krishnakumar Gopalakrishnan's user avatar
2 votes
1 answer
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 ...
Hamideh's user avatar
  • 131
2 votes
1 answer
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 ...
Avv's user avatar
  • 505
2 votes
1 answer
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 ...
rtheunissen's user avatar
2 votes
1 answer
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 <...
nTuply's user avatar
  • 449
2 votes
2 answers
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 ...
user96199's user avatar
2 votes
1 answer
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. ...
Vk1's user avatar
  • 118
2 votes
1 answer
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 ...
matrixone's user avatar
2 votes
1 answer
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 ...
TigerCode's user avatar
  • 121
2 votes
0 answers
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 ...
Eterm's user avatar
  • 129
2 votes
2 answers
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 ...
Thornside's user avatar
2 votes
0 answers
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 ...
jpenna's user avatar
  • 121
2 votes
0 answers
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 ...
Netch's user avatar
  • 141
2 votes
0 answers
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 ...
Rajeev Pandey's user avatar
2 votes
0 answers
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 ...
Daniel Rodríguez's user avatar
2 votes
4 answers
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....
Hazem Alabiad's user avatar
1 vote
3 answers
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 ...
ilam engl's user avatar
  • 151
1 vote
2 answers
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 ...
user avatar
1 vote
2 answers
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: ...
CcVHKakalLLOOPPOkKkkKk's user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
2 answers
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 ...
Simone C.'s user avatar
  • 133
1 vote
3 answers
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 ...
Divyanshu Shukla's user avatar
1 vote
1 answer
329 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 ...
jugc's user avatar
  • 13
1 vote
1 answer
58 views

Does a sorted sequence from in-order traversal imply a binary tree is a BST?

An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the ...
Mason Rashford's user avatar