# 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,744
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 ...
• 456
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

### 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 ...
• 305
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 ...
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,131
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 ...
• 278k
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,565

### 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

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

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

### Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

Using the idea of @Mahyar, I think there is another way to find a solution to the problem. Given a tree $T= (V, E)$, find a bipartition of $T = (X\sqcup Y, E)$ (using a simple graph traversal). ...
• 15.9k
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....
• 278k

### 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 ...

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

Let us consider first the case in which node indices are 1-based (start at 1). The nodes in a heap are arranged so that node $1x_1x_2\ldots x_\ell$ (given in binary) is reached by starting at the root ...
• 278k

### 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 ...
• 181

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 $... • 30.8k 8 votes ### Runtime difference bewteen Union by Rank and Union by Size for union-find If you combine union by rank or union by size with e.g. path compression the amortized complexity is the same [$O(m\alpha(m,n))$]. But notice that Wikipedia uses union by rank in order to prove the ... • 1,629 8 votes ### Comparing two rooted n-ary trees irrespective of the order of children nodes? It's much simpler than isomorphism. For each vertex, check that the parent is the same in both trees. • 16.7k 8 votes ### Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree We can weight vertices such that the entire tree has a fixed sum of weights; for example, zero. Let us design a recursive procedure that assigns weights to the vertices of a tree$T$with root$r$... • 81 7 votes ### Algorithm to find diameter of a tree using BFS/DFS. Why does it work? Update 3 and corrected answer There's an error in the linked solution set (see update 2 below), but it can be easily corrected with @Yuval Filmus's suggestion in the question's comment, which further ... • 858 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 ... • 163k 7 votes Accepted ### Building segment tree without adding extra elements to its size A segment tree is not required to be full (which is what I believe you mean), however it will always be complete. That is, every level, except possibly the last, is filled. Take a look at the ... • 4,511 7 votes ### How to select a binary tree node uniformly at random The algorithm works just fine. Note that each node's size field tells you the total number of nodes in the subtree rooted at that node. Throughout this answer, I'm ... 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,484 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,... • 163k 7 votes Accepted ### Edge exchange property of two Minimum Spanning Trees Here is a proof. Let$V$be the vertices of$G$.$V$are also the vertices of$T$and the vertices of$T'$. If$e$is deleted from$T$, we will get two trees. Let the vertices of these two trees be$(...
• 39k
(This answer expands on Albert Hendriks' approach from the comments.) First idea: let us turn the problem around. As stated, we fix the number of covered edges, $k$, and minimize the maximum length ...