Questions tagged [binary-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
0
votes
2answers
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 $=$.
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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?
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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. ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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. ...
0
votes
1answer
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-...
0
votes
0answers
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? ...
0
votes
1answer
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 ...
0
votes
0answers
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:
0
votes
0answers
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: ...
0
votes
0answers
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=...
0
votes
1answer
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)$**.
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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$ (...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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.
0
votes
0answers
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?
0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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.
-1
votes
2answers
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.
-1
votes
2answers
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
-1
votes
1answer
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)?
-1
votes
1answer
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 ...
-1
votes
1answer
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. ...
-2
votes
1answer
109 views

Prove that if x has a predecessor, this predecessor has a right child

In a BST, Let x be a leaf node, which is a left child of node y. Prove that if x has a ...
-3
votes
1answer
4k views

Constructing binary search tree from given data

The data are in alphabets. U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A. Perform pre, in and post order traversals. I'm confused as how to construct it in the 1st place. Only sense i ...

1
2