28
votes
Accepted
Can the pre-order traversal of two different trees be the same even though they are different?
Tree Examples (image):
...
- 576
17
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 ...
- 369
13
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 ...
- 3,108
10
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 ...
10
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,
...
- 376
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 ...
- 279k
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 ...
- 29.6k
8
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,
...
- 72.9k
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 $...
- 31.1k
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 ...
D.W.♦
- 166k
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 ...
- 4,662
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,...
D.W.♦
- 166k
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 ...
- 31.6k
6
votes
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 ...
D.W.♦
- 166k
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....
- 16.9k
6
votes
Accepted
An α-good tree with n nodes has height O(log n)
$$2|y| = (|y|-|z|) + (|y|+|z|)\le \alpha |x| + |x| - 1.$$
So, $|x| \ge \frac2{1+\alpha}|y|$.
Since $y$ is an arbitrary child of $x$, if node $x$ is of height $k$, $|x| \ge \left(\frac2{1+\alpha}\right)...
- 39.1k
6
votes
Accepted
Are reversed reverse preorder traversals equivalent to a postorder traversal?
This can be proven by induction on trees. I give details on the conjecture 1 here.
It is clearly true for the empty tree and for leaves;
Suppose it is true for trees $l$ and $r$. Consider $t$ a node ...
- 16.9k
5
votes
Binary Search Tree Traversals
The rules for traversing a tree are, to visit all nodes of a tree you do this:
Preorder: (1) visit the root node, then (2) visit all the nodes in the left subtree of the root, then (3) visit all the ...
- 14.9k
5
votes
Find the longest possible path in full binary tree
If it is a full binary tree, that is defined as:
Full binary tree is a tree in which every node other than the leaves has two children.
Then you know the depth $D$ will be half of the total ...
- 4,523
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 ...
D.W.♦
- 166k
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 ...
- 1,215
5
votes
Accepted
Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves
As @Rick Decker explained, you could have $n/2$ leaves at the max depth in the one case. In this case, step 3 is $O(n\log n)$. This post shows the worst case. Consider a tree $T$ consists of a chain ...
- 1,041
5
votes
Accepted
For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes
$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are ...
- 2,221
5
votes
Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers
You can use a balanced BST. For each node $n$, let $n.lsize$ be the size of the left subtree of $n$. Insert and delete is just standard BST add and remove with size updating. To implement ...
- 2,788
5
votes
An α-good tree with n nodes has height O(log n)
First, note that if $T$ is an $\alpha$-good tree, then for any node $x$ with children $y$ and $z$, without loss of generality, $|y| \leqslant |z| <\frac{1+\alpha}2 |x|$.
Now consider $h_n$ the ...
- 16.9k
5
votes
Are reversed reverse preorder traversals equivalent to a postorder traversal?
Nathaniels simple and elegant proof is the best way to formally convince yourself your conjectures are true. I want to add a more informal and visual explanation.
The postorder traversal of a binary ...
- 31.1k
5
votes
Accepted
Improving a ranking system with "best rank"
Each query can be implemented to run in $O(\log n)$ time by lazily propagating appropriate operators on the binary search tree.
The lazy propagation technique *1, is that it is possible to perform ...
- 2,942
4
votes
Delete a range of keys in a binary search tree in better than $O(n\lg n)$?
You might be interested in a data structure called TeardownTree. It supports delete_range operation that works in $O(k + \log n)$ time, where $n$ is the initial ...
- 41
4
votes
Hash tables versus binary trees
GCC C++ case study
Let's also get some insight from one of the most important implementations in the world. As we will see, it actually matches out theory perfectly!
As shown at https://stackoverflow....
4
votes
Accepted
Number of different binary search trees storing n distinct keys?
The solution to your recurrence is
$$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$
also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the ...
- 279k
Only top scored, non community-wiki answers of a minimum length are eligible