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

## What is the insertion algorithm for an AVL tree with balance constraint of 2?

What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?

## Do you have to have seen a tree in person to use Transport Via Plants

Transport Via Plants says

You must have seen or touched the destination plant at least once before.

If you used scrying on someone and see a plant that could be used for the spell can you teleport through that plant?

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

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:

for example, here, the node with the value 6 returns $$$$, and the NULL node to the right of the root returns $$$$; 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$$:

But, shouldn’t the end result be this?