28 votes
Accepted

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

Tree Examples (image): ...
royashcenazi's user avatar
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 ...
ihadanny's user avatar
  • 369
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 ...
HEKTO's user avatar
  • 3,068
9 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 ...
Romantic Electron's user avatar
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 ...
Yuval Filmus's 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, ...
CR Drost's 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 ...
Steven's user avatar
  • 28.5k
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 $...
Yuval Filmus's 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 $...
Hendrik Jan's user avatar
  • 29.9k
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.'s user avatar
  • 156k
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, ...
Raphael's user avatar
  • 72.1k
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 ...
Narek Bojikian's 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,...
D.W.'s user avatar
  • 156k
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 ...
gnasher729's user avatar
  • 28.4k
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 ...
Pseudonym's user avatar
  • 21.7k
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 ...
hengxin's user avatar
  • 9,501
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.'s user avatar
  • 156k
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....
Nathaniel's user avatar
  • 12.5k
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)...
John L.'s user avatar
  • 38.6k
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 ...
Nathaniel's user avatar
  • 12.5k
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 ...
ryan's user avatar
  • 4,431
5 votes
Accepted

Every AVL tree may be red black tree

Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule: Every path from a given node to any of its descendant NIL nodes contains the ...
Yuval Filmus's user avatar
5 votes

Depth first or breadth first ordering in binary search trees?

Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so ...
templatetypedef's user avatar
5 votes

Help with proof involving weighted full binary tree

There are two basic induction patterns for (non-empty) full binary trees: A tree is either a leaf or consists of a root and two full binary subtrees. A tree is either a leaf or can be obtained from a ...
Yuval Filmus's user avatar
5 votes
Accepted

Depth first or breadth first ordering in binary search trees?

There's a paper on this: Khuong and Morin. Array Layouts For Comparison-Based Searching They compare the Eytzinger, B-Tree, Van Emde Boas, and sorted array layouts and conclude that Eytzinger works ...
KWillets's user avatar
  • 1,274
5 votes
Accepted

Is a balanced binary tree a complete binary tree?

A complete binary tree is a binary tree of length $h$ such that all the levels from $1$ to $h-1$ are completed and the last level gets completed from left to right. As in the image below. A balanced ...
anon's user avatar
  • 156
5 votes
Accepted

How many number of different binary trees are possible for a given postorder (or preorder) traversal

Every binary tree (with the right number of nodes) has exactly one labelling that satisfies a given postorder labelling. So you need to find the number of binary trees. That is the famous Catalan ...
Hendrik Jan's user avatar
  • 29.9k
5 votes
Accepted

KD-Tree implementation with lat/lon coordinates

Short answer: No, you will not get the same results. It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into ...
Evil's user avatar
  • 9,425
5 votes
Accepted

Why is this not a valid Red-Black tree?

If you go to the empty leaf from the root in the pattern [Right, Left], you get to an empty leaf encountering 1 black node. If you go [Right, Right, Left] or [Right, Right, Right], you get to an empty ...
Cricket's user avatar
  • 66
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 ...
Rick Decker's user avatar
  • 14.8k

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