## relation between steiner tree and Edge-disjoint paths in trees

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

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