91 votes
Accepted

What's the difference between a binary search tree and a binary heap?

Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you ...
user avatar
  • 1,092
49 votes

What's the difference between a binary search tree and a binary heap?

Summary ...
user avatar
37 votes

What's the difference between a binary search tree and a binary heap?

Both binary search trees and binary heaps are tree-based data structures. Heaps require the nodes to have a priority over their children. In a max heap, each node's children must be less than itself. ...
user avatar
  • 1,711
28 votes
Accepted

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

Tree Examples (image): ...
user avatar
20 votes
Accepted

What are the main ideas used in a Fenwick tree?

A Fenwick tree is a binary tree used to efficiently handle cumulative frequencies or sums in an array. Without loss of generality we shall examine a 16-element array. Imagine a binary tree imposed on ...
user avatar
18 votes
Accepted

Does a graph always have a minimum spanning tree that is binary?

There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $...
user avatar
  • 22.1k
14 votes
Accepted

When are binary trees better than hashtables in real world applications?

Hash tables can only tell you if an element is present or not. Here are somethings you can do with a binary tree that you can't do wiht a hash table. sorted traversal of the tree find the next ...
user avatar
  • 522
14 votes

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 ...
user avatar
  • 339
13 votes

What's the difference between a binary search tree and a binary heap?

With data structure one has to distinguish levels of concern. The abstract data structures (objects stored, their operations) in this question are different. One implements a priority queue, the ...
user avatar
  • 27.6k
12 votes

Size of decision tree and depth of decision tree

The depth of a decision tree is the length of the longest path from a root to a leaf. The size of a decision tree is the number of nodes in the tree. Note that if each node of the decision tree ...
user avatar
  • 141k
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

When are binary trees better than hashtables in real world applications?

One application domain where binary trees are better, or more easily adjustable than certain alternatives, are persistent data structures (which are often used in (purely) functional programming). A ...
user avatar
9 votes
Accepted

Range update + range query with binary indexed trees

Suppose you had an empty array: 0 0 0 0 0 0 0 0 0 0 (array) 0 0 0 0 0 0 0 0 0 0 (cumulative sums) And you wanted to make a range update of +5 ...
user avatar
  • 406
9 votes

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

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, ...
user avatar
  • 366
9 votes

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 ...
user avatar
  • 23.4k
8 votes
Accepted

Lower bound of a summation with an exponential

There is a general formula for this sum: $$ \sum_{h=0}^m h2^h = \sum_{h=1}^m \sum_{k=1}^h 2^h = \sum_{k=1}^m \sum_{h=k}^m 2^h = \sum_{k=1}^m (2^{m+1}-2^k) = m2^{m+1} - (2^{m+1}-2). $$ Overall, we get $...
user avatar
8 votes
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 ...
user avatar
8 votes

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

Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $...
user avatar
  • 27.6k
7 votes
Accepted

Number of Different AVL Tree

Let $a_{n,h}$ denote the number of AVL trees with $n$ nodes and height $h$. It is straightforward to get a recurrence for $a_{n,h}$: $$a_{n,h} = \sum_{k=1}^n \bigl(a_{k-1,h-1}a_{n-k,h-1} + a_{k-1,h-1}...
user avatar
  • 6,519
7 votes
Accepted

When inserting into a binary tree, is there a universal agreed upon place to insert then new node to minimize complexity?

There are several different concepts here. Let's start from the most general. A tree is a data structure that consists of a root and a collection of children, each of which is a tree. A node of the ...
user avatar
7 votes

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

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, ...
user avatar
  • 70.9k
7 votes

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

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,...
user avatar
  • 141k
7 votes

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 ...
user avatar
  • 25.2k
6 votes
Accepted

Check whether it is possible to turn one BST into another using only right-rotations

If $T_1$ and $T_2$ don't encode the same sequence, they are not right-convertible into each other (obviously). This can be tested in linear time by inorder traversal of both trees. The following ...
user avatar
  • 6,519
6 votes

Why aren't tries generally used?

This is an interesting question. Certainly worth asking. The choice of a data structure is very much dependent on what you want to do with it. A more costly sophisticated structure, no matter how ...
user avatar
  • 19.1k
6 votes
Accepted

Huffman Code VS Hu–Tucker Code

Let me give you a real-world example, that's very similar to something I wrote once. Let's say you're implementing a library catalogue system. A library catalogue is conceptually a collection of ...
user avatar
  • 18.9k
6 votes
Accepted

Maximal difference of height between two leaves in an AVL tree

We consider Fibonacci tree ([TAOCP3, Knuth98, Sect. 6.2.1]) and compute the maximal height difference in it. A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of ...
user avatar
  • 9,209

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