Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

### Can the pre-order traversal of two different trees be the same even though they are different?

Tree Examples (image): ...
• 576

### BIT: What is the intuition behind a binary indexed tree and how was it thought about?

I think that the original paper by Fenwick is much clearer. The answer above by @templatetypedef requires some "very cool observations" about the indexing of a perfect binary tree, which are ...
• 369
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 ...
• 3,088

### Can the pre-order traversal of two different trees be the same even though they are different?

Counting argument The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes, ...
• 376
Accepted

### How are binary trees represented on disk

This may not be an exact answer but some information of interest related to your question Other answers have mentioned various ways in which the binary data structure can be represented and you might ...

### Time Complexity to find height of a BST

Your algorithm runs in linear time on all inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number ...
• 277k

### Find the number using binary search against one possible lie

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the ...
• 29.5k
Accepted

• 30.8k

### Have I invented a new data structure?

I've never seen this data structure before. However, it doesn't seem like a good choice for storing a set of words, for most purposes. I see three significant disadvantages: Performance. Looking up ...
• 160k

### How are binary trees represented on disk

There are many ways to represent trees, each with their own set of advantages and disadvantages. Here's an incomplete list: Use any graph representation, e.g. adjacency matrix, incidence matrix, ...
• 72.5k

### What is the point of traversing a binary tree in preoder, inorder or postorder?

Different traversals of a binary tree exist to suffice different data dependencies between the nodes. Let's have a comparison between different traversals of a tree. Note that aside from in-fix ...
• 4,474

### Can the same node appear twice in a tree?

A tree is defined to be a set of nodes, with a parent-child relationship that satisfies certain properties. Thus, it doesn't make sense to ask whether a node can "appear" twice. In your code snippet,...
• 160k

### Find the number using binary search against one possible lie

If normal binary search would take k questions, then you can solve this with 2k+1 questions: Ask each question twice. If you get the same answer, it was the truth. If not, a third question reveals the ...
• 30.4k

### If both could be implemented with the other, what are the differences between priority queues and binary heaps?

Based on standard usage of the terms, a heap is a specific data structure, with a specific representation in memory. A priority queue is an abstract data type: it identifies some operations that must ...
• 160k
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....
• 15.7k