# Questions tagged [binary-search-trees]

The tag has no usage guidance.

125 questions
Filter by
Sorted by
Tagged with
9 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 ...
32 views

### How to trasnform search tree into AVL tree with constant memory and in linear time?

How to transform search tree into AVL tree with constant memory and in linear time ?
46 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 ...
40 views

### Minimum absolute difference in a BST is always between

Given a Binary Search Tree(BST) I would like to understand can absolute minimum difference between any two nodes of a BST is always between adjacent nodes. If Yes or No can we generalize it ? Assume ...
26 views

### When can a (max) heap be a BST?

Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below: A heap can never be a BST A heap is ...
22 views

### Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time

We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time. We can do this in linear time but with extra ...
34 views

### Calculating the expected height of a randomly built binary search tree

I need to calculate the expected height of a randomly built binary search tree, BST, with 4 different keys: $x < y < z < w$ According to Catalan numbers, there are 14 possible trees, 8 with ...
34 views

### Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$

I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key[x] + key[y] = 2 \cdot key[p(x, y)]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$...
49 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 ...
21 views

### BST deletion of node with 2 children by copying right child to predecessor

I try to delete a node, $z$, with 2 children in binary search tree by exchanging $z$'s right child and $z$'s predecessor, $y$, right child, which is NULL because $y$ has no right child, if it had then ...
75 views

### Suggest a Data Structure that support the following operations with time complexity O(log(n))

I’m looking for a data structure that supports that store the salaries of it’s employees. Insert(e) – Insert employee e into the data structure. AvgDecile(k) – Returns the average salary of the k’th ...
41 views

### Average depth BST upper bound

I have a question regarding the BST average depth upper bound. Following the proof from Data Strucutures and Algorithms in Java by Weiss (3rd edition), I was wondering if there was some kind of ...
33 views

### For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
23 views

### Converting Binary Search Tree into Decreasing Ordered Linked List

Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the ...
50 views

### If a key in a red-black tree has exactly one child (which isn't null) then it is always red

I have the following claim: Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red. My attempt: Disproof. We will exhibit a counterexample: ...
40 views

### Are there any trees where Preorder$(T_1) =$ Preorder$(T_2)$ and Inorder $(T_1) =$Inorder $(T_2)$, but $T_1 \neq T_2$?

Is it possible for two binary trees $T_1 \neq T_2$ that both Preorder and Inorder traversal are equal ?
109 views

115 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, ...
457 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 ...
63 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 ...
33 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
38 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-...
1k 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 ...
3k 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 ...