The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [trees]

Questions about a special kind of graphs, namely connected and cycle-free ones.

Filter by
Sorted by
Tagged with
4
votes
1answer
62 views

E-Unification: “Goal seeking” pattern matching between directed trees

Preamble Suppose we have some symbols x, y, ... and wildcards (ξ), ...
0
votes
1answer
936 views

Optimal data structure for sorted list

Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)". Even though B-trees are a generalization ...
0
votes
2answers
247 views

How does a Trie work?

Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree. The problem though is that after reading ...
0
votes
1answer
54 views

Choose minimum subset of edges in tree that connects all important nodes

Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$. We want to choose subset of edges of the tree such that: For each two important nodes at least one edge ...
1
vote
1answer
127 views

A way to convert a binary tree into a grid

Wondering if there is a way to convert a binary tree into a grid such as this: ...
1
vote
1answer
121 views

Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties

What is an algorithm that will take as an input a flat list of objects with a varying degree of overlapping properties: ...
1
vote
1answer
470 views

How a range query works on a simple B+tree

Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following: ...
2
votes
2answers
388 views

Infix search in millions of strings

Let's say we have millions of strings (each of them < 100 characters): alpha allo blah hello world orlando ... I know how a binary search tree or a trie can ...
0
votes
0answers
141 views

Data structure for a single elimination tournament and its implementation

I want to implement a tournament managing software , something like challonge(https://challonge.com/) and am currently stuck at the data structure to be used. I read up on tournament trees and a ...
0
votes
1answer
82 views

Transform 2D range query matrix into segment tree to make memory usage lower

Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-...
0
votes
0answers
33 views

In what case would bi-directional BFS have the same asymptotic run time as a regular BFS?

I'm not quite sure when they would have the same asymptotic running time. Would it be if the graph was each node connected to one other node in a line? I know that for a bi-directional BFS to have a ...
3
votes
1answer
133 views

Is there a name for this tree traversal?

This came when I was looking at block scoping in compiler design. { A { B } { C {D} {E} } } For the above pseudo code, the order in which the scope ...
1
vote
0answers
46 views

Do we need visited flags when applying BFS on a tree?

Do we need visited boolean flags when applying BFS on a tree ? ...
1
vote
1answer
100 views

Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, ...
0
votes
0answers
45 views

Finding a certain subset of a weighted tree

Given a rooted tree with $n$ weighted nodes and a number $1\leq k\leq n/2$, what is an efficient algorithm for finding a subset of the nodes having $k$ elements no node being an ancestor of another ...
2
votes
1answer
326 views

How to read off the set represented by a van-Emde-Boas tree?

I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
2
votes
0answers
122 views

Algorithm to find nodes with given a distance

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
3
votes
1answer
38 views

Minimum edge cover with a constraint

An edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. I am interested in finding the minimum edge cover of a tree such that each ...
0
votes
0answers
19 views

Doubt regarding deletion from a B-tree

After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for ...
7
votes
1answer
133 views

Prefix Sums in Mutable 2D Array

Suppose I have a 2D array M[n][n] of integers (in fact, binary is fine, but I doubt it matters). I am interested in repeated queries of the form: given a coordinate ...
0
votes
0answers
32 views

Cross link suggestion algorithm that distributes and spans all links as fast as possible without loops

I am implementing a topic suggestion system to a website. The aim is to add links to the left panel of each topic. For example, I opened the topic named "topic1", left of the page should show 5 ...
1
vote
1answer
51 views

Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this? I know ...
1
vote
1answer
57 views

Complexity for find pairs with sum - BST

I have written an algorithm for find all the pairs in a BST which have a given sum. ...
2
votes
1answer
99 views

Set partition refinement with subtrees

In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary ...
-2
votes
1answer
234 views

Obtain data structure able to do reverse range updates

For given array $A$ of size $N$, note that the array is going to be permutation of the numbers from 1 to N, each number will be there exactly once, we want to obtain data structure being able to ...
2
votes
1answer
235 views

How to partition a tree on a fixed budget of edge cuts?

Suppose I have a tree $T=(V,E,w)$ with vertex weights $w(v)\ge 0$ for all $v\in V$. I want to partition this tree into $k+1$ trees by cutting $k$ edges such that the deviation from the mean of the ...
5
votes
4answers
3k views

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

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the indicies of the children of element at index n can be found with $...
0
votes
0answers
244 views

Code arithmetic expression in a binary tree

How to present (code into) an expression consisting of brackets and following operations: +, -, / and * into a binary tree. Then, I need to write an algorithm that will derive that very tree. Any ...
1
vote
1answer
152 views

Understanding B tree key deletion step from CLRS algorithm

CLRS explains B tree key deletion as follows: If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$. If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
0
votes
1answer
42 views

k-means clustering with efficient point lookup?

What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still ...
0
votes
0answers
49 views

Find K least values in a Tree in which each node has 4 children

Here is an example tree: Each node has either $0$ or $4$ nodes. The values $v(n)$ of the node $n$ is given by $v(n) = v(\operatorname{parent}(n)) + k(n)$, where $k(n)\in \{2, 2.5, 8, 50\}$, such that ...
2
votes
2answers
656 views

Is there a way to calculate exactly how many binary trees are possible if only one of the preorder, inorder and postorder traversals is given?

I am studying tree traversals and I've got to know that we can uniquely determine the binary tree if their: Case 1. Preorder & inorder traversals are given or Case 2. postorder & inorder ...
1
vote
0answers
38 views

Number of binary trees of size $n$ such that all subtrees of same size are equal?

For a binary tree $t$, let the size $|t|$ be the number of leaves of $t$. I am interested in the following property of a binary tree $t$: If two subtrees $t'$ and $t''$ of $t$ have the same size, i.e. ...
4
votes
1answer
47 views

How do 2-3 FingerTrees generalize to bigger branching factors?

FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
1
vote
1answer
35 views

Is graph search of shortest (optimal) path an instance of optimisation?

I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm. I am not too familiar with graphs / trees ...
1
vote
1answer
192 views

Why do we need binary trees when we have multi branch trees? [closed]

Why do we need binary trees when we have multiway trees. Are binary trees even used. Are they used only for teaching the concepts of trees?
0
votes
2answers
6k views

Order of a leaf node in B+ Tree

Going with the definition, that order of a B+ tree is the maximum number of children a node can have. What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node ...
1
vote
1answer
33 views

Highly colored vertices in greedy coloring imply existence of subtrees

I have a graph $G$ on which I try greedy coloring; i.e. I order the vertices and then start coloring them according to their order and I assign each vertex the smallest possible color available to it. ...
0
votes
1answer
323 views

#3-Coloring Problem for Tree with Some Pre-Colored Nodes [closed]

I have a undirected tree and three colors to choose from. Some nodes are already colored; these nodes and their colors are given. What is an efficient algorithm to find the number of ways to color the ...
4
votes
1answer
69 views

Common parse tree for several formulas

I have a large (~1k) number of boolean formulas like: f1(x) = p1 AND p2 f2(x) = (p1 AND p2) OR p3 f3(x) = p4 OR !p5 The argument x is a set, and the predicates (...
0
votes
0answers
25 views

Proof of Zig-Zig step

There was a question connected with one of the video lecture lessons that I'm currently watching. Let two trees be given - the original and the tree after the zig-zig step: Calculate the cost of ...
1
vote
1answer
622 views

The maximum number of nodes in a heap tree of degree d and depth k

The maximum number of nodes in a binary tree of depth k is defined by 2^(k+1)-1, but the same rule doesn't appear to work for heap trees of different degrees. Let's say I have the following tree of ...
2
votes
1answer
107 views

Question about the difference between radix trees and patricia trees

I've already done some research on this topic, but it still isn't quite clear to me. According to this post patricia trees are radix trees with $r = 2$. Every patricia tree I've seen so far is used ...
3
votes
0answers
451 views

How can we describe the similarity between trees?

For example, I have a program generates two ASTs, and I want to compare the two trees. I've tried to treat the trees as graphs, but I think it doesn't show the particularity of trees.
2
votes
1answer
236 views

Dynamic programming tree algorithm

We have a network of sensors organized in tree form, where the sensors occupy the nodes. Most of the time the sensors are turned off, until the root sensor wakes up the rest of the sensors. This ...
0
votes
1answer
171 views

Number of 2-3 trees of depth 4

I have a task to find a number of 2-3 trees... I don't quite know what it means, I'm asked to: find the number of 2-3 trees of depth $4$? Is there a specific way to find number of 2-3 trees of depth $...
1
vote
2answers
1k views

Find a node with maximum distance from query node in a tree

I solved this problem from codechef: problem link and now I want to change it a bit. Instead of find out the distance between node $u$ and $v$ I want to answer $k$ queries of the form: find node $u$ ...
4
votes
1answer
609 views

Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

This is from CLRS problem 24.3-5: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$ . Give ...
1
vote
1answer
216 views

How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$?

How to prove that for a full (each node that's not a leaf has 2 nodes) binary tree $T$ of $n$ leaves there's a series of frequencies $f_1,f_2,...,f_n$ such that if we use Huffman algorithm on the ...
8
votes
3answers
7k views

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

Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?