# 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 ...
• 379
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 ...
• 2,977

### 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 ...
• 6,940

### 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 ...
• 11.8k

### 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 ...
• 161
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....
• 7,193

### 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 ...
• 143k

### 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 ...
• 1,145
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 ...
• 270k

• 8,937
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 ...
• 270k
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. ...
• 34.7k