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

inserir a descrição da imagem aqui

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