# Questions tagged [trees]

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

566 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
1answer
51 views

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: ...
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. ...
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 ...
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 ‘...
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 ...
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 ...
0answers
48 views

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