# Questions tagged [binary-search-trees]

The tag has no usage guidance.

89 questions
Filter by
Sorted by
Tagged with
40 views

### Modifying insert and remove functions of an AVL tree so that nodes that don't need to be rebalanced are not checked for balance

Trying to modify an insert and remove function for an AVL Tree so that no nodes are checked for balance that do not need to be. The suggested way to do was was to change the return types of insert, ...
27 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 ...
23 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)$**.
44 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 ...
32 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-...
32 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).
517 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: ...
99 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, ...
14k 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 ...
31 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
34 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 ...
2k 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 <...
152 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 ...
52 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 ...
32 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 ...
590 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....
22 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 ...
19 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 ...
111 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)?
83 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 ...
524 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.
143 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 ...
243 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?...
58 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 ...
25 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?
77 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 ...
40 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 $=$.
31 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$ (...
81 views