# Questions tagged [binary-search-trees]

The tag has no usage guidance.

99 questions
Filter by
Sorted by
Tagged with
176 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 ...
14 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$ ...
31 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-...
18k 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 ...
730 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....
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? ...
97 views

### Binary Tree Node Insertion

I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript. I was thinking especially about the node insertion method. Here's my ...
140 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 ...
37 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)$**.
60 views

### Calculate number of nodes in all subtrees without using DFS

Is it possible to calculate the number of nodes using post-traversal order, instead of using DFS? Below is an illustration of the question:
649 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: ...
13 views

### Data structure for revising ordering given a (largely) ordered stream of data

I have an input stream of timestamped data that is largely sorted in ascending order by timestamp. There are occasionally out-of-order elements, at which point I need to do each of the following: ...
126 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 ...
29 views

### How many Binary Search Trees are there which have N nodes and their height is log N

How many Binary Search Trees are there which have N nodes and their height is log N ? We need a recursive function to solve this problem. For example if n=2 the answer is 2. If n=3 answer is 1 . If n=...
212 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 ...
41 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: ...
40 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 ...
147 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 ...
34 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-...
34 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).
104 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, ...
32 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
40 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 ...
4k 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 <...
1k 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 ...
282 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 ...
49 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 ...
30 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 ...
25 views

### AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?

I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them ...
156 views

### All the possible inputs for a given AVL tree

Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?
703 views

### Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences

Given inorder and preorder (or postorder) traversal sequences of a binary tree balanced binary tree binary search tree of n nodes, what is the time complexity of creating the respective unique tree.
206 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 ...
832 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?...
69 views

### Which binary search trees have constant time rebalancing time at min/max?

Given that I'm already at either the min or the max node of a binary search tree, which balanced variant would require only constant time bottom-up rebalancing after an update (add new min/max, or ...
33 views

### Finding Binary Search Tree Height, What happens to duplicates?

I'm going over past exam papers with this question: The answer to a). will be (height of 5): For b.): I assume the height function will be to find the height of the tree. So, I will have to compare ...
1k 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?
162 views

### Tracing BST Pseudocode for Insertion

I'm having real trouble tracing some pseudocode for insetion into a Binary Search Tree. I need to understand this in order to be able to teach it, but I think there are flaws in the material. For ...
46 views

### Algorithm for searching in BST with only <

How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $<$ on the key type. The ones I can easily also requires $=$.
Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (...