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
49 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
55 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
79 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
182 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
206 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
2k 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
238 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
122 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
38 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
46 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
600 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
36 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
0answers
41 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
179 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
5k 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
32 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
293 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
59 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
378 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
97 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
338 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
208 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
168 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
862 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
500 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
200 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
6k 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?
1
vote
1answer
178 views

Increasing every starting edge by a constant, then the shortest path tree remains the same?

Consider a directed graph G = (V,E) with non-negative costs on each edge. With s being a starting vertex. Prove that by adding ...
5
votes
3answers
1k views

How to select a binary tree node uniformly at random

The exercise I'm trying to solve is You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method ...
2
votes
1answer
67 views

What is the type system (or class of type systems) that that ensures all your tree Branches end in Leaves?

I've come across this situation numerous times in the past few years where I have some classes like (pseudo-Java): ...
1
vote
1answer
36 views

Is it possible to obtain dynamic tree with two dimensions in big matrix

Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions). In some of the coordinates of the matrix ...
4
votes
1answer
93 views

Is there a polynomial algorithm for optimal sorting on trees?

There's the classical problem of sorting numbers in a list with the restriction that you can only swap two neighbouring numbers. It's easy to see that getting an optimal number of needed swaps can be ...
1
vote
1answer
131 views

Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent

Show that for any leaf v in a binary search tree, if u is the parent of v, then either key[v] is the largest key in the tree smaller than key[u], or key[v] is the smallest key in the tree larger than ...
4
votes
0answers
53 views

Repeated nearest-neighbor queries

If I want to make N repeated (i.e. millions of) 2D nearest-neighbor queries on a pointset of size M, is traveling down into a KD-Tree most efficient or are there better ways to do this? (e.g. Voronoi?)...
1
vote
0answers
340 views

How to calculate multibit trie storage size?

I wish to use a multi-bit trie structure for storing IPv4 forwarding information with a fixed stride width of 8 bits, I think this is also called a "radix of 8" (so for any IP prefix 4 levels will ...
3
votes
1answer
425 views

Depth of a leaf in a prefix tree (Huffman Coding)

So, regarding Huffman Coding we know that the optimal way of "storing" it is using a full binary tree (where all nodes have either 0 or 2 children). All leaves are the symbols $i$ of the alphabet we ...
2
votes
0answers
195 views

Semi-automatic layout algorithms for a mind map

There're some existing tree layout algorithms such as Tidier Drawings of Trees and Drawing Non-layered Tidy Trees in Linear Time. I call them as automatic layout algorithms since positions of nodes ...
1
vote
1answer
359 views

Minimum number of edges to add such that there are no bridges on a tree

Any edge of a tree is a bridge. What is the minimum number of edges that I will need to add so that there are no more bridges in a tree? I have seen the solution from the internet the answer is $\frac{...
1
vote
0answers
217 views

Maximizing book picked using two stacks

There are two stacks(S1 and S2) of books. Each book in stack has a weight. You are given a net weight(W) of books that can be picked. You have to maximize the number of books that can be picked. Note ...
1
vote
1answer
79 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
117 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
285 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
50 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
127 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 ...