The actual question is :
Write a program that takes as input a general tree T and a position p of T and converts T to another tree with the same set of position adjacencies, but now with p as its root.
I am not sure what does it means by the position adjacencies exactly but from what I understood is that the relation between the parent as the nodes should be maintained.
But if a node is made to be the root then they wont be having the same positional adjacency. I would like to implement this question using a binary tree for starters.
Can someone help me out with how should I implement it?
The quote uses some terms which should be further defined, but I will try to make some assumptions here:
...but now with p as its root.
This implies that the tree given as input is a so-called rooted tree and not just a general tree as it states at the outset. It is important to note this, as in graph theory a tree is just a graph where each pair of nodes is connected by a single path. The concept of root only enters the story when we speak of a rooted tree.
...a position p of T...
This is uncommon terminology. I'll assume that position is a synonym for what is generally called a vertex or node in graph theory.
... position adjacencies
I'll assume that this is referring to the edges of the tree.
... the relation between the parent as the nodes should be maintained.
If you phrase it that way, then it is impossible to change the tree, as the set of parent-child relationships uniquely defines the rooted tree. So we must assume that this is not about maintaining the parent-child relationship, but just the relationship between two vertices, where possibly the role of parent may be changing.
I would like to implement this question using a binary tree for starters.
That is not a good idea: a binary tree may need to transition to a non-binary tree. For example, let's say the input tree is this binary tree:
4
/
2
/ \
1 3
And the input vertex is the one with value 2. That means the output tree will not be binary, but will be:
2
/|\
1 3 4
So, we have a rooted tree and a vertex in that tree as input, and need to produce a rooted tree as output whose root is that given vertex.
The algorithm can be recursive:
p (that should become the root) has no parent, nothing needs to change: exitp's parent has no parent, since p's parent has become the root.p from its parent, and instead make that parent a child of p. So these two nodes remain connected, but the role of parent-child switches to child-parent.Here is an implementation in JavaScript. You can run the snippet here on an example graph:
8
/ \
4 10
/
2 <-- to become new root
/ \
1 3
Resulting tree should be:
2
/|\
1 3 4
\
8
\
10
class Node {
constructor(value) {
this.value = value;
this.children = new Set; // any number of children
this.parent = null;
}
addChild(node) {
this.children.add(node);
node.parent = this; // back reference
return node;
}
detachFromParent() {
if (this.parent != null) {
this.parent.children.delete(this);
this.parent = null;
}
}
makeRoot() {
let parent = this.parent;
if (parent != null) {
parent.makeRoot();
this.detachFromParent();
this.addChild(parent);
}
}
print(indent="") {
console.log(indent + this.value);
indent += " ";
for (const child of this.children) {
child.print(indent);
}
}
}
// demo
let eight = new Node(8);
let ten = new Node(10);
let four = new Node(4);
let two = new Node(2);
let one = new Node(1);
let three = new Node(3);
eight.addChild(four);
eight.addChild(ten);
four.addChild(two);
two.addChild(one);
two.addChild(three);
console.log("input:");
eight.print();
console.log("change root to 2...");
two.makeRoot();
two.print();