# Questions tagged [binary-search-trees]

The tag has no usage guidance.

100 questions
Filter by
Sorted by
Tagged with
965 views

### Day-Stout-Warren algorithm for balancing BST. How does vine to tree work?

I was trying to understand the dsw algorithm for balancing a binary search tree in-place using this virgina tech page. The wikipedia page and vt page are more or less similar. I am having a hard time ...
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 $=$.
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 ...
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 ...
83 views

### avl trees rotations question

As you can see in this tree its unbalanced at the root with a balanced factor of $-2$. You can also perform a Right left rotation or a Right Right rotation. Which do you have to pick in this case?
291 views

### What happens internally when you remove an object from a treemap

I am wondering what happens if you remove an object in the middle of a treemap. If the treemap would look something like this: So what would happen if you remove the number 30? Because 27 and 34 ...
19 views

### Call stack is hard to maintain in my brain. What should I?

When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and ...
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$ ...
229 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 ...
151 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 ...
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 ...
295 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 ...
50 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 ...
2k views

### Calculation of Inorder Traversal Complexity

I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
282 views

### All possible Red Black Trees with this set {1,2,3,4,5}

I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}. Now we have 120 ways to write 1,2,3,4,5 ...
62 views

### Complexity for find pairs with sum - BST

I have written an algorithm for find all the pairs in a BST which have a given sum. ...
43 views

### k-means clustering with efficient point lookup?

What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still ...
214 views

### Is there an example of an AVL tree that is taller than a binary heap?

I am curious because I took a quiz and answered false to the question: "The height of an AVL tree may be greater than the height of a binary heap with the same elements." I have been trying to think ...
736 views

### When to rebalance the AVL tree?

Consider we have an AVL tree. Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left ...
179 views

### Merging two binary search tress

You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$ nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys in tree B. ...
33 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-...
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? ...
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 ...
65 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:
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: ...
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=...
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)$**.
178 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 ...
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 ...
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 ...
164 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 ...
34 views

### Augmenting a tree such that we preserve the insertion operation optimal runtime

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$ (...
73 views

### The validity of the potential function for splay tree

The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in ...
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 ...
116 views

### Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder

I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.
47 views

### AVL Tree Inner Nodes

If k is the height of an AVL Tree, the minimal number of inner nodes is: N(k) = N(k-1) + N(k-2) +1. Why is this formula true?
123 views

### An AVL tree is a BST, but AVL tree can be not complete, then why do we define AVL tree a BST?

An AVL tree is a BST, and a BST is a complete tree, but AVL tree doesn't necessarily have to be complete. Thus, why do we define AVL tree a BST?
452 views

### How to find point of maximum overlap in both X and Y Axis?

I was given a array R of n rectangles [each element in the array is a bottom left point(x1,y1) and a top right point (x2,y2)] , parallel to the axis, and an array P of n points [each element is a ...
32 views

### Binary Search Tree: If two different traversals are given, will there be a unique tree that satisfies the traversals? [duplicate]

I have come across algorithms that can create a BST if any two of the 3 traversals are given (there would be three different algorithms for the 3 combinations) This is an example I was wondering, is ...
120 views

### IO efficiency of a complete binary search tree

I was given this as a homework exercise, yet I don't know whether my solution is sound: Given a complete binary search tree where blocks are formed in order of the value of the nodes. What would ...
67 views

### Find keys between $x$ and $y$ in binary search tree

Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
707 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.
2k views

### Time complexity of searching an element in Binary Search Tree [closed]

I want to know what will be the time complexity to search, insert and delete an element in a) balanced binary search tree. b) unbalanced binary search tree.
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
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)?
317 views

### Simulating AVL Tree Right, then Left rotation

I have the following AVL tree and want to AVL-INSERT a node 5 into the tree. Since the middle branch will be unbalanced, I'm guessing that it will require a right rotation, then a left rotation to ...
534 views

### Binary search trees: multiple Successor() calls

Show that, given a tree node a, the time complexity of calling k times to Successor() is $O(k+h)$, where $h$ is the tree height. ...