consider an instance of steiner tree such that at each iteration we connect new required vertex with shortest path to T that T formed previously with this strategy .I want find relate between Edge-disjoint paths in trees and T to find approximation factor logn for steriner tree

# Tag: tree

## behavior tree – is there any different solution for different buildings different behaviours

```
class agricultural{
Workr Work
void Working(Work W){
Behaviour1();
}
}
class Carpentry{
Workr Work
void Working(Work W){
Behaviour2();
}
}
template <tipename T> class BuildWork{
T BW
Work(){
BW.Working();
}
}
```

something like that but problem occurs as when I would wont to declare template

```
class Workr{
// here I would need to make it only for 1 is possible
BuildWork <agricultural> BW
}
```

so this is no use or is it?

so next thing occured to me is this

```
class Building{
bool beh(2);
void Work(Workr W){
if beh(0){
if (beh(1)){
behaviour0(Workr W);
}
else{
behaviour1(Workr W);
}
}
else{
if (beh(1)){
behaviour2(Workr W);
}
else{
behaviour3(Workr W);
}
}
}
}
```

the last code is workable but I wander if there is any better solution to be made thanks

PS. if code isn’t logically made I’m sorry as I cam only use hospital’s computer and I’m programming with pencil on a piece of papres

## c – Find Binary Tree Path Sum

I am trying to resolve following problem. Please advice which part of the code can be improved.

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Example:

Given the below binary tree and sum = 22,

```
5
/
4 8
/ /
11 13 4
/
7 2 1
```

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Implementation:

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct stTree
{
struct stTree * left;
struct stTree * right;
int value;
} stTree;
struct stTestCase
{
stTree *root;
int sum;
bool result;
};
stTree* createNode(int value, stTree *leftNode, stTree *rightNode)
{
stTree *node = malloc(sizeof *node);
if (!node) abort();
node->left = leftNode;
node->right = rightNode;
node->value = value;
return node;
}
bool hasPathSum(const stTree *root, int sum)
{
if (!root) return false;
if (!root->left && !root->right)
{
if (sum == root->value)
return true;
else
return false;
}
return (hasPathSum(root->left, sum - root->value)
| hasPathSum(root->right, sum - root->value));
}
static stTree* findBottomLeft(stTree *node)
{
while (node->left)
node = node->left;
return node;
}
void freeTree(stTree *node)
{
if (!node) return true;
stTree *bottomLeft = findBottomLeft(node);
while (node)
{
if (node->right)
{
bottomLeft->left = node->right;
bottomLeft = findBottomLeft(bottomLeft);
}
stTree *old = node;
node = node->left;
free(old);
}
}
int main(void)
{
struct stTestCase test_cases(3)={
{
createNode(5,
createNode(4,
createNode(11,
createNode(7, NULL, NULL),
createNode(2, NULL, NULL)), NULL),
createNode(8,
createNode(13, NULL, NULL),
createNode(4, NULL,
createNode(1, NULL, NULL)))),
22,
true
},
{
createNode(5,
createNode(1,
createNode(11,
createNode(3, NULL, NULL),
createNode(2, NULL, NULL)), NULL),
createNode(7,
createNode(13, NULL, NULL),
createNode(4, NULL,
createNode(1, NULL, NULL)))),
22,
false
},
{
createNode(12,
createNode(4,
createNode(11,
createNode(7, NULL, NULL),
createNode(51, NULL, NULL)), NULL),
createNode(8,
createNode(13, NULL, NULL),
createNode(4, NULL,
createNode(6, NULL, NULL)))),
22,
false
}
};
for(int i=0; i<3; i++)
{
if (hasPathSum(test_cases(i).root, test_cases(i).sum) == test_cases(i).result)
printf("test case (%d), PASSn", i);
else
printf("test case (%d), FAILn", i);
freeTree(test_cases(i).root);
}
}
```

RESULT:

test case (0), PASS

test case (1), PASS

test case (2), PASS

## Binary search tree implementation C++

I currently learning about bst i looking for simple binary search tree implementation in c++ only add, remove, search and calculate height of the tree

## python – Ternary Search Tree find max word

I need to write a maximum function so that it finds that longest word in the Ternary Search Tree and prints it.

This is what I have done so far. I have words in the tree such as “canvas”, “cats” “van” but it prints None any way.

```
def maximum(self):
if self.root == None:
return 0
ptr = self.root
self.maxLengthTST(ptr)
def maxLengthTST(self,ptr):
if ptr.left == None:
return
if ptr.next == None:
return
if ptr.right == None:
return
return max(self.maxLengthTST(ptr.left), self.maxLengthTST(ptr.next)+1, self.maxLengthTST(ptr.right));
def max( a, b, c):
max = 0
if a >= b and a >= c:
max = a
elif b >= a and b >= c:
max = b
else:
max = c
return max
```

## Numbering a binary tree – Computer Science Stack Exchange

Given a binary tree, consisting of node objects with a left and a right child respectively, how could I add a label to each node s.t. the root has label 1,1 , in the second level the left node has 2,1 and the right node has 2,2 and so on. I’m already given a binary tree and can add properties to the node object. I’m not allowed to rebuild the binary or sth. like this, and I thought about somehow using recursion.

## Unable to resolve dependency tree – Instalação da biblioteca Material-UI

Erro na instalação da biblioteca Material-UI

## c++ – Segment tree and queries

I studied segment tree recently and I made this code of segment tree and its queries. Is my code correct in terms of time complexity?

```
class segmentTree{
private:
vector<int> mini;
vector<int> tree;
vector<int> maxi;
int n;
```

Here in the constructor I passed the dynamic array.

```
public:
segmentTree(vector<int> a)
{
mini=a;
tree=a;
maxi=a;
n=tree.size();
}
```

makeTree function builds three segment trees for different queries like sum, maximum and minimum.

```
void makeTree()
{
reverse(tree.begin(),tree.end());
reverse(mini.begin(),mini.end());
reverse(maxi.begin(),maxi.end());
for(int i=0;i<tree.size();i+=2)
{
tree.pb(tree(i)+tree(i+1));
mini.pb(min(mini(i),mini(i+1)));
maxi.pb(max(maxi(i),maxi(i+1)));
}
tree.PB();
mini.PB();
maxi.PB();
reverse(tree.begin(),tree.end());
reverse(mini.begin(),mini.end());
reverse(maxi.begin(),maxi.end());
}
```

The sum function calculates the sum of given range.

```
int sum(int a,int b)
{
a+=(n);
b+=(n);
int sum=0;
while(a<=b)
{
if(a%2==1)
{
sum+=tree(a-1);
a++;
}
if(b%2==0)
{
sum+=tree(b-1);
b--;
}
a/=2;
b/=2;
}
return sum;
}
```

The minimum function finds the minimum value of given range.

```
int minimum(int a,int b)
{
a+=(n);
b+=(n);
int minu;
while(a<=b)
{
if(a%2==1)
{
minu=mini(a-1);
a++;
}
if(b%2==0)
{
minu=mini(b-1);
b--;
}
a/=2;b/=2;
}
return minu;
}
```

The maximum function finds the maximum value of given range.

```
int maximum(int a,int b)
{
a+=(n);
b+=(n);
int maxu;
while(a<=b)
{
if(a%2==1)
{
maxu=maxi(a-1);
a++;
}
if(b%2==0)
{
maxu=maxi(b-1);
b--;
}
a/=2;b/=2;
}
return maxu;
}
};
```

## Bash/zsh function that cd to the root of git tree

I’d like to get a review for the function, that cd into the git tree root, or does nothing if we are outside of the repository

```
# cd to the root of the current git directory
# If $PWD is submodule, will cd to the root of the top ancestor
# It requires to stay in the current directory, if the root is . or unknown,
# and use cd only once, to have a way to do `cd -`
function cg {
git_root() {
local super_root
local top
top="$(git rev-parse --show-cdup)"
top="${top:-./}"
super_root="$(git rev-parse --show-superproject-working-tree)"
if (( "$super_root" )); then
printf '%s' "$top../"
( cd "$top../" && git_root || return )
fi
printf '%s' "$top"
}
local git_root
git_root="$(git_root)"
( "x${git_root}" != "x./" ) && cd "$(git_root)" && return || return 0
}
```

## approximation – any one can help for finding tight example of steiner tree with shortest path?

1.Consider arbitrary permutation of $R={s_1,s_2,…,s_alpha }$

2.Set $Tleftarrow{s_1} $

3.$forall_{iin {2,3,…,alpha}}$

Let $P_i leftarrow$ shortest path that connecting $s_i$ to $T$

$T= Tcup P_i$

4.Return $T$

my prove is:

proof upper bound of algorithm