16 votes

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 ...
user avatar
  • 379
12 votes
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 ...
user avatar
  • 2,977
11 votes

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 ...
user avatar
  • 6,940
10 votes

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 ...
user avatar
6 votes

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 ...
user avatar
6 votes
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....
user avatar
  • 7,193
5 votes

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 ...
user avatar
  • 143k
5 votes

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 ...
user avatar
  • 1,145
5 votes
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 ...
user avatar
4 votes

how does rotation works in AVL trees and what is a good way to understand it?

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: $...
user avatar
  • 27.7k
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 ...
user avatar
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 \...
user avatar
  • 620
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 ...
user avatar
  • 143k
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 ...
user avatar
  • 1,635
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 27.7k
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 ...
user avatar
  • 71k
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 ...
user avatar
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 ...
user avatar
  • 5,910
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 25.4k
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 ...
user avatar
  • 1,145
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 ...
user avatar
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.
user avatar
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 ...
user avatar
3 votes
Accepted

Observations about the structure of an optimal Binary Search Tree

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 ...
user avatar
3 votes
Accepted

How does the Inorder-tree-walk algorithm move to a different node after hitting a leaf?

To understand what happens "when we hit the node with the key 11", let us isolate the call Inoder-tw(node17), which executes the following. ...
user avatar
  • 34.7k
3 votes
Accepted

Height of AVL Tree

The AVL invariant does not guarantee that, given any two tree paths, their length differs at most by one unit. They can differ by more than one unit, as shown by the following tree (Fibonacci AVL tree ...
user avatar
  • 14.2k

Only top scored, non community-wiki answers of a minimum length are eligible