# Tag Info

Accepted

### What is the difference between radix trees and Patricia tries?

I found this post very helpful. To see the difference between Patricia tries and radix trees, it is important to understand: The notion of radix, since Patricia tries are radix trees with radix ...
• 3,454
Accepted

### Is there a difference between perfect, full and complete tree?

Yes, there is a difference between the three terms and the difference can be explained as: Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full ...
• 406
Accepted

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

Tree Examples (image): ...
• 566
Accepted

### What are the applications of Rose trees?

You seem to have an overly "data structures and algorithms" mindset. Not every tree is some kind of search tree. Data structures are often designed to correspond to or capture aspects of a domain ...
• 11.8k

### 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 ...
• 339
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 ...
• 522

### Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

The intuition behind is very easy to understand. Suppose I have to find longest path that exists between any two nodes in the given tree. After drawing some diagrams we can observe that the longest ...
• 185

### What is the earliest use of "trees" in computer science?

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857. Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they ...
• 80.4k
Accepted

### Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

Found this which states that if all the conditions I mentioned above are met, a graph necessarily has a unique MST. Therefore, in terms of my question, Kruskal's and Prim's algorithms necessarily ...

### 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 ...
• 667
Accepted

### What does pre-, post- and in-order walk mean for a n-ary tree?

No, it's not limited to binary trees. Yes, pre-order and post-order can be used for $n$-ary trees. You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the ...
• 143k

### What is the earliest use of "trees" in computer science?

According to Donald Knuth's TAOCP, Vol. 1, pg. 459 the following papers might be considered as one of the first appearances of trees in CS. H. G. Kahrimanian, Analytical Differentiation by a Digital ...
• 11.9k

### Longest path in an undirected tree with only one traversal

This can be solved in a better way. Also, we can reduce the time complexity to O(n) with a slight modification in the data structure and using an iterative approach. For a detailed analysis and ...
• 200
Accepted

### Binary rooted tree isomorphism

There is a classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman. The algorithm actually uses a simple isomorphism invariant. See for example lecture notes of ...
• 270k
Accepted

### What algorithm should I use to find a minimal tree that include certain nodes within a graph?

This is the famous Steiner tree problem in graphs, which is known as NP-hard.
• 7,275
Accepted

### Count total number of k length paths in a tree

This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th ...
• 1,066
Accepted

### What is the difference between a R-tree and a BVH?

Note that we want to be able to retrieve, for any query range, the points that are inside, or sometimes the points that are closest to that query range. That's why a bounding-volume hierarchy is ...
• 1,914
Accepted

### Why is the running time for BFS $O(b^{d+1})$?

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to ...
• 143k

### Why does the formula 2n + 1 find the child node in a binary heap?

I would like to propose my revisited version of Hiroki's answer. Currently it's been sitting in peer-review (https://cs.stackexchange.com/review/suggested-edits/66932) for a while, so it's not being ...
• 91

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

### 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, ...
• 366
Accepted

### How can one search in O(log n) time in a red-black tree?

The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are ...
• 2,209
Accepted

### Is the height of the tree the number of edges or number of nodes?

As Yuval says, there's no standard definition. This is not because computer scientists are indecisive but because it's sometimes more convenient to use one definition and sometimes more convenient to ...
• 80.4k
Accepted

### What is the chance that this code terminates?

This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the ...
• 270k
Accepted

### Time complexity of Depth First Search

The book is counting the number of times each line is executed throughout the entire execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT....
• 270k

### Why is the running time for BFS $O(b^{d+1})$?

The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is ...
• 80.4k