# Tag Info

### Why use binary search trees when hash tables exist?

The most obvious answer is that trees can be traversed in their natural order very efficiently. If you need to visit every element of a dictionary in alphabetical order, a tree can support this ...
Accepted

### What is "rank" in a binary search tree and how can it be useful?

According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with ...

### If inorder traversal of a tree is in ascending order will the tree definitely be a BST?

Yes. The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST ...

### Why use binary search trees when hash tables exist?

Binary search trees (BSTs) of various sorts and their variations are widely used data structures today, so they are hardly a "historical note". For example, both the .NET Framework and the Java ...

### Why use binary search trees when hash tables exist?

You are right now thinking of a data structure from which just three operations are expected, Insertion Lookup Deletion But if you extend these range of operations, to let's say finding number of ...
Accepted

### Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Long story short: it is possible in constant time if the tree is a full binary tree. If not, there are some cases where there is not enough information to find the size of the subtree in constant time....

### Balanced Binary Search Tree Two-Sum with Constraints

I don't know how to do this is in $O(n)$ time and $O(1)$ space, but I can show you how to do it in $O(n)$ time and $O(\lg \lg n)$ space. In particular, given any tree of depth $O(\lg n)$, I'll show ...

### Why is Binary Heap never unbalanced?

You must refer to the definition of a Binary Heap: A Binary heap is by definition a complete binary tree ,that is, all levels ...
Accepted

### Big O vs. Big Theta for AVL tree operations

This is a pedantic point which I suggest ignoring. The intended interpretation of the "worst case" column seems not to be the worst-case complexity, but rather bounds on the complexity which ...

One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other. The operation can be seen as a associative property: $... 4 votes Accepted ### BST representation of Hash Tables What the author means by implementing a HashTable as a BST is simply implementing a BST with$insert(), \space delete() \space and \space search()$with slight modifications The node of the BST would ... 4 votes Accepted ### Algorithm for searching in BST with only < If what you mean is that you want to build a BST and you only have the$<$operation, and you only know the algorithms with the$\leq$operation, you can notice that :$$a \leq b \Leftrightarrow \... 4 votes ### Algorithm for searching in BST with only < You can test whether$a=b$as follows: if it's not true that$a<b$and not true that$b<a$, then it follows that$a=b$. (Disclaimer: this requires that it be possible to order all of the ... 4 votes ### Why is Binary Heap never unbalanced? The question is a little confusing, since a binary heap is usually implemented in an array, not a tree. The tree is used for visualization. Consider the following heap: It is given by the following ... 4 votes Accepted ### Height of epsilon-balanced binary search tree Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's$n$nodes. For the second vertex, it's at most ... 4 votes ### is it possible to create an avl tree given any set of numbers? AVL trees are a kind of binary search trees. As such, they implement the following operations, among else: Initialize an empty tree. Add a value to the tree. Remove a value from the tree. Search a ... 4 votes Accepted ### is it possible to create an avl tree given any set of numbers? Your question is not the right one. An AVL tree is a binary tree that has additional properties. First it is a search tree, which means we can easily find each number in the tree. Second it is ... 4 votes Accepted ### finding an algorithm for creating a priority search tree in linear time with presorting What you are looking for is essentially a Cartesian tree: The Cartesian tree for a sequence of distinct numbers can be uniquely defined by the following properties: The Cartesian tree for a sequence ... 3 votes ### What is the advantage of leaf trees vs. node trees? You don't quote the reasoning of P. Braß, if he gives any, so we can only guess. I would like to distinguish two cases. Data are stored as values, i.e. in place. Data are stored by reference. In ... 3 votes ### Data structure for handling intervals Since all intervals are non-overlapping, the use of an interval tree is unnecessary. We will store our intervals in an AVL tree$T$sorted by start points and use the fact that bulk deletion of a set ... 3 votes Accepted ### Why do we use multiple data structures? Aspects other than asymptotic worst case time are also important. For example Actual speed in practice Memory consumption Implementation difficulty Algorithmic analysis almost never tells you the ... 3 votes Accepted ### Should all internal node keys in B+ tree also be in the leaves? The internal keys come from values also stored in leaves, but if you allow deletions, the value could be deleted from the leaf after it is created and used in the internal node. Deleting the value ... 3 votes Accepted ### Facts about internal and external path lengths of binary tree I'm assuming the following model for a binary search tree of size$n$. Consider the following infinite process. At step 0, we have the empty tree. At step 1, we have the tree having some arbitrary ... 3 votes ### Why use binary search trees when hash tables exist? The two disadvantages of hash tables: 1. They don't support ordering. Search trees naturally support processing all items in sorted order, or processing all items in some range. 2. The speed will ... 3 votes ### Calculation of Inorder Traversal Complexity In order to analyse the time complexity of a tree traversal you have to think in the terms of number of nodes visited. If a tree has$n$nodes, then each node is visited only once in inorder traversal ... 3 votes ### in order of binary search tree Remember that an in-order traversal lists the elements from left-to-right, descending the tree: Left, Root, and ... 3 votes Accepted ### Inorder tree tranversal on binary search tree doesn't give the elements in order? This is not a valid binary search tree, since 26 is greater than 20 and is in its left subtree. 3 votes Accepted ### Splay Tree: Repeatedly searching for the same key that's not in the Tree In a BST, a lookup for an key that isn't present traces out a path through that tree that ends at either that key's successor or that key's predecessor. We'll use this property to get the desired$O(m ...
Let us prove by induction on depth that for every node $v$, there exist $a_v,b_v$ (possibly $\pm \infty$) such that the input $x$ reaches $v$ iff $a_v < x < b_v$. This is true for the root since ...