Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
85 views

Name for tree where each node has the aggregate of its children

Is there a general name for a tree in which the leaves have some arbitrary values and the value of every other node is some "aggregate" function of its children? An example where the aggregate ...
0
votes
0answers
118 views

Recursive algorithm for counting pairs of ancestor and child, where sum =n

Hey, this is a question from my handouts, but how would I go about writing a recursive program that would return the number of pairs of an ancestor and a child, whose sum equals to n, given that the ...
1
vote
1answer
22 views

Closed (visited) list in state-space search - How do I make it efficient?

As part of an assignment for an AI class that I'm taking, I'm need to solve a puzzle on a 4x4 grid using breadth-first search (each element can take on 12 different values). There is a maximum of 4 ...
1
vote
1answer
39 views

Storing nodes in state space search

I'm taking an introductory course in AI and we've been given the assignment to solve a puzzle using different search algorithms on a state space (BFS, DFS etc). I understand the theory and everything, ...
1
vote
0answers
86 views

Update and find-smallest-absolute-value operations on a tree

I have a balanced binary tree that stores a number in each node, initially zero. I want to build a data structure that will support the following two operations: Given a vertex $v$ in the tree and a ...
4
votes
1answer
291 views

Tree with branching factor 1

Something that has been bothering me for a while is the formula for the maximum amount of nodes of a tree with height d and branching factor of b. $$(b^{d+1}-1)/(b-1)$$ This holds true for all ...
1
vote
1answer
51 views

Is there a name for the “tree” aproach to listing things?

I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question. Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 ...
1
vote
0answers
129 views

Generic tree with minimum weighted path length problem

Suppose there are an undirected graph $G = (V, E)$ and a function $f : V \rightarrow \mathbb{R}$, which associates a weight for each vertex in $G$. I was wondering if it is possible to find a tree $T =...
1
vote
0answers
37 views

Alternative to CELL+ATOM as “the ultimate data representation form”

The construct of a cell (an ordered pair with pointers to either another cell or an atom) and atom (an indivisible sequence (of bits) (i.e. a natural number)) is a fundamental data structure for many ...
1
vote
1answer
576 views

Number of rooted labelled trees

According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2 If the tree is rooted then in each tree we can ...
1
vote
1answer
128 views

Merge Leaf labeled trees [closed]

I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to ...
2
votes
1answer
216 views

What is the branching factor for nondeterministic games?

Given a nondeterministic game how could one know the branching factor of it? Is it the number of all possible outcomes? I have an example game in which you have some cards. The goal is to get rid of ...
3
votes
1answer
334 views

Building segment tree without adding extra elements to its size

I recently learned about segment trees as data structures, and what I learned was that we are always building segment tree with size $N$ such that $N$ is power of two. If $N$ is not power of two we ...
1
vote
1answer
1k views

Show that run time complexity of operations on 2-4 tree is $O(\lg n)$

I just studied about this 2-4 tree which is a self-balanced tree. Various sources and textbook often mentioned that the insertion, deleting and searching of this tree is $O(\lg n)$. However, none of ...
3
votes
1answer
181 views

How many different trees can we form from given graph?

I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$ In this graph I want to count the sub-...
3
votes
2answers
302 views

Heights series in the DFS traversal of a binary tree

Assume a binary tree of height N. All nodes have exactly 2 children and all leaves have height N. For example, the following tree has N=3: ...
2
votes
0answers
146 views

K-ary tree that wrapped around

I'm not sure the best way to name this problem, but basically I need to construct a complete $k$-ary tree for $k \geq 2$ which has this nice property as $k=1$ tree that we can create a ring out of it. ...
1
vote
0answers
33 views

Is there a “diminishing returns” tree search algorithm?

I'm looking for an algorithm that will let me plug in a heuristic for scoring a subtree, and as the algorithm does a depth-first search, it stops when the score has: Already hit a threshold (minimum ...
1
vote
5answers
275 views

“Smallest set” term in the trees set definition

I often meet such kind of the definition of the set of trees, as: The set of unranked $\Sigma$-trees, denoted by $T$, is the smallest set of strings over $\Sigma$ and the parenthesis symbols ‘)’ and ‘...
1
vote
1answer
239 views

Example of Random Binary Tree?

I'm trying to understand what a random binary tree is. According to Wikipedia: Two different distributions are commonly used: binary trees formed by inserting nodes one at a time according to a ...
4
votes
1answer
116 views

Minimum Number of People Such That No Two People Know the Same Two People

In a population of $n$ people, each person knows $k$ other people and each person is known by the same $k$ people. However, no two people, p1 and p2, know the same two people p3 and p4. What is the ...
0
votes
0answers
48 views

Tracking Solution with Multiple Matrices in Dynamic Programming

We recently figured out a Dynamic Programming solution to compare two trees using concepts of edit distance in strings. It goes something like this- $A[i', i, j', j] = \min \begin{cases} B[i', i-1, ...
2
votes
2answers
116 views

Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time

Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and constant space. The original problem appears here, ...
0
votes
0answers
101 views

Ancestor with a specific color

During a lot of algorithm competitions I met colored tree questions and there have been multiple cases where I though of different approaches. I'm curious what is the best way of solving the following ...
5
votes
1answer
338 views

What is the minimum required storage for a sparse, depth-first octree?

For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree ...
1
vote
1answer
792 views

Find all intervals that are contained in a query interval

Given a set of intervals $S = I_1, ..., I_n$, what is the fastest way to find all intervals of $S$ that are completely contained in an interval $I_\text{query}$? It should also support incremental (...
5
votes
1answer
125 views

Monte Carlo Tree Search in connect 5 tree design

I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm: The initial state, S0 is the board state where the ...
2
votes
0answers
62 views

stacks in tree constructions

There are two nice tree constructions, that use a stack in a similar manner: Construct a binary search tree from a pre-order traversal (e.g. see http://www.geeksforgeeks.org/construct-bst-from-given-...
0
votes
1answer
773 views

What is the height of avl tree with n nodes [closed]

what is the height of avl tree with n nodes ? Can you explain it with formula ? I couldn't find any formula to solve this problem.
0
votes
0answers
24 views

How to find the maximum element in a multi-tree under logN time?

Here N represents the number of elements in the multi-tree. Please state the algorithm that you have used to do so. It would be great if you can implement this in Java/C++ too and post the code as ...
0
votes
1answer
424 views

Code to count number of leaves of a tree? [closed]

I've just started learning C. Can anyone tell me whether my code is correct or not, if not what's the correct version? This is code for counting number of leaf nodes. Is this efficient one if this is ...
1
vote
1answer
856 views

Rotations in a treap

I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done. Image 1 Image 2
4
votes
2answers
1k views

Have I invented a new data structure?

EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th ...
0
votes
1answer
215 views

Link-cut trees: how to code cut(u,v)

In most bibliography, only cut(v) is defined. More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree. The pseudo-code and code for this is: ...
4
votes
3answers
4k views

how is data in a tree stored in memory?

I am not so familiar with trees. How is a tree stored in memory? what is the data structure type used for storing it? As a string?linked list? stack (!)? Or is there some kind of data storage model ...
1
vote
1answer
381 views

Trie traversal to maximise XOR in a tree but with a condition

Input:I am provided with x and y. x is a 32 bit non negative integer and y is some node-id of the tree. So, I built a trie with 32-bit non negative integer values which are the keys associated with ...
3
votes
1answer
390 views

Link-cut trees: using access() and link()

I am having some trouble on understanding link-cut trees, so I need some help. Suppose that we have nodes $A, B, C, D$ and we want to do the following operations: Link(A,B) Link(B,C) Link(C,...
1
vote
1answer
65 views

Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)

I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials) ...
0
votes
0answers
53 views

Tree algorithm to calculate greatest k

Given a tree, where each node holds a unique number, each of these numbers is represented in $O(log\,n)$ bits. Describe an algorithm to calculate the greatest number $K$ there is. I would like to ...
-1
votes
1answer
133 views

The longest path in a tree

Help me demonstrate this or there is a counterexample? Let $T(V,E)$ be a tree with $|T| \geq 2$ and a path $P{(u_0,u_1,u_2,...,u_n)}$. The longest path in a tree has $d(u_0) = d(u_n) = 1$.
0
votes
1answer
32 views

R-Tree multipath search - remember the path?

R-Trees can take several paths to retrieve an item because of overlaps in data being indexed or index structure. However, if we run the same search many times on the same unmodified structure, can we ...
1
vote
1answer
1k views

Efficient Algorithm to compute radius of tree

Given an acyclic undirected graph alike to this one : (Here the center is the node '2', and the radius is 5) What is the most efficient (ideally in O(n)) way to ...
0
votes
1answer
202 views

How important is balance of a tree?

I am exploring variations of trees. I know that a quality which is sometimes desired is balance in the tree so that tree depth is reduced. But I am imagining that in situations in which several paths ...
1
vote
0answers
137 views

Edge coloring optimization using dynamic programming

The problem is to find an algorithm that colors all the edges in any arbitrary tree T with a root r, let's say in blue and red, such that the number of blue edges is maximal and there isn't more than ...
0
votes
2answers
733 views

Algorithm to find path with max sum of degrees in a tree structure

Is there an efficient way to find a path from root to a leaf such that it has the maximum sum of degrees of nodes from all the paths possible in the tree. For example if a tree is defined as the one ...
1
vote
1answer
870 views

Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
0
votes
0answers
34 views

Number of possible balanced binary trees [duplicate]

A tree is balanced if the subtrees of each node differ in height by at most one. How many balanced binary trees can we create from $n$ nodes?
3
votes
0answers
890 views

Lowest single common ancestor in a Directed Acyclic Graph?

I was reading how to find the Lowest common ancestor in a DAG. A DAG can have scenarios where the LCA yields multiple solutions and I feel the accepted answer explains that pretty well. However, one ...
1
vote
1answer
93 views

A closed form expression for # of inputs of a binary tree and its number of nodes

Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes? In case that the binary tree is a full tree, it is ...
0
votes
1answer
379 views

Strict-Binary Tree - Same Post-order & Pre-order sequences?

I'm going through some past exam papers for my course and I'm having trouble completing this one question. It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order ...