Minimum spanning tree with small set of possible edge weights

Given a undirected graph which only has two different edge weights $ x$ and $ y$ is it possible to make a faster algorithm than Prim’s algorithm or Kruskal’s algorithm?

I saw on Kruskal’s algorithm that it already assumes that the edges can be sorted in linear time with count sort, so then can we gain any benefit by knowing the weights of all of the edges ahead of time?

I don’t think there is any benefit, but I am not sure…

Dynamic Program for Tree based question

You are given a tree T where every node i has weight wi ≥ 0. Design a polynomial time algorithm to find the weight of the smallest vertex cover in T. For example, suppose in the following picture wa = 3, wb = 1, wc = 4, wd = 3, we = 6. Then, the minimum cost vertex cover has nodes a, b with weight 3 + 1 = 4.

enter image description here

In the question, the opt i am chosing is OPT(v,boolean) is a min weight vertex cover for subtree v and boolean means whether it contains v or not. What are the subproblems that are formed and how do I move ahead? any hint is helpful.

Merge $k$-sorted arrays – without heaps/AVL tree in $O(n\log(k))$?


Given $ k$ -sorted arrays in ascending order, is it possible to merge all $ k$ arrays to a single sorted array in $ O(n\log(k))$ time where $ n$ denotes all the elements combined.

The question is definitely aiming towards a Min-heap/AVL tree solution, which can in fact achieve $ O(n\log(k))$ time complexity.

However i’m wondering if there exists a different approach, like a merge variant which can achieve the same result.

The closest I’ve seen is to merge all the arrays into one array which disregards their given ascending order, than doing comparison-based sort which takes $ O(n\log(n))$ but not quite $ O(n\log(m))$ .

Is there an algorithm variant which can achieve this result? Or a different data-structure?

check if a binary tree is a binary search tree

I have some doubts about this algorithm which checks if a binary tree is a binary search tree:

isAbr(x)     {             if(x == NULL)                     return <true, -∞, +∞>;             if(x.left == NULL && x.right == NULL)                     return <true, x.key, x.key>;              <abrLeft, minLeft, maxLeft> = isAbr(x.left);             <abrRight, minRight, maxRight> = isAbr(x.left);             abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);             min = MIN(minLeft, minRight, x.k);             max = max(maxLeft, maxRight, x.k);              return <abr, min, max>     } 

in particular, it is not clear to me what happens when a node has only one child:

enter image description here

for example, here, the node with the value 6 returns $ <true, 6, 6>$ , and the NULL node to the right of the root returns $ <true, -∞, + ∞>$ ; but with the instruction abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft); don’t we get FALSE $ (8 < -∞)$ ?

checks if a tree is a full binary tree

I have to write an algorithm that checks if a tree is full binary tree (each node, except the leaves, must have 2 children), but I don’t know if this version is correct.

 isComplete(u)  {         if(u == NULL)                 return false         else         {                 left = isComplete(u.left);                 right = isComplete(u.right);                 complete = left && right;                  return complete.         } } 

Insert a node in a binary search tree

The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $ z.p = y$ instruction does. wouldn’t the algorithm work without it?

abr_insert(T, z) //z is the node that must be inserted     {             y = NULL;             x = T.root;             while(x != NULL)             {                     y  = x;                     if(z.key < x.key)                             x = x.left;                     else                             x = x.right;             }             z.p = y; //here is the instruction that I don't understand             if(y = NULL)                 T.root = z;             else if(z.key < y,key)                     y.left = z;             else                     y.right = z;     } 

Deletion in a Binary search Tree

The teacher explained to us this algorithm for deleting a node in a binary search tree, but I can’t understand how it works when the node to be deleted has only one child (I already know how it works theoretically).

Algorithm:

abc_delete(T, z) // z is the node that must be eliminated  {         if((z.left == NULL) && (z.right == NULL))                 y = z;         else                 y = abr_successor(z);          if(y.left != NULL)                     x = y.left;         else                     x = y.right;          if(x != NULL)                 x.p = y.p;          if(y.p == NULL)                 T.root = x;         else         {                 if(y == (y.p).left)                         (y.p).left = x;                 else                         (y.p).right = x;         }          if(y != z)                 z.key = y.key;         return y; }  abr_successor(x) {         if(x == NULL)                 return NULL;         if(x.right != NULL)                 return abr_min(x.right)         y = x.p;         while(y != NULL && x = y.right)         {                 x = y;                 y = y.p;         }         return y; } 

For example, I want to delete the node number $ 7$ : enter image description here

But, shouldn’t the end result be this? enter image description here