Questions tagged [subtree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

fastest algorithm to count leaf nodes (i.e. terminal nodes)

With the following recursive code to count leaf nodes of a binary tree, is there any way to make it faster or parallel-computing optimized in time? Python code - (mag(P) = number of leaf nodes of tree ...
Ten's user avatar
  • 119
1 vote
2 answers

Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?

I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for ...
Fausto Zamparelli's user avatar
3 votes
1 answer

Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order. I believe that I understood the three terms pretty well, and ...
Rodrigo's user avatar
  • 189
1 vote
1 answer

Uniformly random iteration of subtrees

I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $...
anlew's user avatar
  • 13
0 votes
2 answers

Get mathematical relation of node IDs of a subtree based on a given tree

(I was not really sure in which "stackexchange" I should put this question. I hope CS is ok.) Let's say I have the following tree A. Every node has a unique ID, which will be counted up, beginning ...
eljobso's user avatar
0 votes
1 answer

Computing a subproduct tree

Consider the following description of a subproduct tree. We define a tree T for some points x[0] to x[n-1], and define m = log_2(n). Tree T is represented as a matrix where each row-column entry i, ...
H W's user avatar
  • 3
1 vote
1 answer

Check if given vertices form a connected subtree in a graph

The approach described in this question is wrong. It'll find false positives for disconnected components with multiple vertices. See D.W.'s answer for a reliable alternative. This might be a simple ...
Fasermaler's user avatar