awwsmm/PNode.java

## PNode.java
import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.stream.IntStream;


public class PNode <K,V> {

  //----------------------------------------------------------------------------
  //
  // Think of nodes like a family tree...
  //
  //  - each node has a value associated with it (knowledge of something)
  //    - value can be null ("I don't know")
  //    - two nodes (people) can have the same or different knowledge (values)
  //
  //  - each node has a label (name)
  //    - two nodes with the same parent can have the same name (why not?)
  //    - labels can be null (old ancestor whose name is unknown)
  //
  //  - value and label can BOTH be null, actually
  //    - children are indexed, so we can refer to them by indices, at least
  //
  //  - also, value and label can be identical among siblings
  //    - (think: twins born to the same parents with the same names)
  //    - just have to "index" them based on time of birth
  //
  //  - when a child is removed (deceased), its index is not freed
  //    - will always be "the first child" etc. of its parent
  //    - child node set to null to maintain node indexing
  //
  //----------------------------------------------------------------------------

  public K label = null; // nodes have labels for easy searching within tree
  public V value = null; // value and label can both be null, because...

  // children of a node are held in a List, so nodes are indexed
  private List<PNode<K,V>> children = new ArrayList<>();
  private      PNode<K,V>  parent   = null;

  ///---------------------------------------------------------------------------
  ///
  ///  constructors
  ///
  ///---------------------------------------------------------------------------

  // create a root node (with no parent)
  public PNode(K label, V value) {
    this.label = label;
    this.value = value;
    // parent remains null
    // children List begins empty
  }

  // create a child node
  public PNode(K label, V value, PNode<K,V> parent) {
    this.label  = label;
    this.value  = value;
    this.parent = parent;
    parent.children.add(this);
  }

  ///---------------------------------------------------------------------------
  ///
  ///  methods to add children to, or remove children from, this node
  ///
  ///---------------------------------------------------------------------------

  // add child with label and value to children
  public PNode<K,V> addChild (K label, V value) {
    return addChild(new PNode<K,V>(label, value));
  }

  // add a single child
  public PNode<K,V> addChild (PNode<K,V> child) {
    if (child != null)
      child.setParent(this);
    return child;
  }

  // add multiple children at once
  public void addChildren (Collection<PNode<K,V>> children) {
    if (children == null || children.size() == 0) return;
    for (PNode<K,V> child : children)
      addChild(child);
  }

  // remove a single child
  public PNode<K,V> removeChild (PNode<K,V> child) {
    if (child == null) return null;
    int index = childIndex(child);
    if (index >= 0) {
      child.parent = null;
      this.children.set(index, null);
    } return child;
  }

  // remove multiple children at once
  public void removeChildren (Collection<PNode<K,V>> children) {
    if (children == null || children.size() == 0) return;
    for (PNode<K,V> child : children)
      removeChild(child);
  }

  ///---------------------------------------------------------------------------
  ///
  ///  methods to change or remove this node's parent
  ///
  ///---------------------------------------------------------------------------

  // set the parent of this node
  public boolean setParent (PNode<K,V> parent) {

    // if parent = null, call removeParent()
    if (parent == null) return removeParent();

    // if this is already the parent, do nothing
    if (parent.equals(this.parent)) return false;

    // otherwise, set new parent
    if (this.parent != null)
      this.parent.removeChild(this);
    this.parent = parent;
    parent.children.add(this);

    return true;
  }

  // remove this node's parents (make it a root node)
  public boolean removeParent() {

    // if null parent, return false
    if (this.parent == null) return false;

    // otherwise, remove this node's parent
    // and remove this child from the parent's children (set to null)
    PNode<K,V> retval = this.parent.removeChild(this);
    return (retval == null) ? false : true;

  }

  ///---------------------------------------------------------------------------
  ///
  ///  methods to get this node's parent and child(ren)
  ///
  ///---------------------------------------------------------------------------

  // get the index of this exact child
  public int childIndex (PNode<K,V> child) {
    return children.indexOf(child);
  }

  // get all children of this node
  public List<PNode<K,V>> getChildren() {
    return Collections.unmodifiableList(children);
  }

  // get the parent of this node
  public PNode<K,V> getParent() { return parent; }

  ///---------------------------------------------------------------------------
  ///
  ///  methods to get more distant relatives: descendants, leaves, roots, etc.
  ///
  ///---------------------------------------------------------------------------

  // get every node that descends from this node
  public List<PNode<K,V>> getDescendants() {

    List<PNode<K,V>> descendants    = new ArrayList<>();
    List<PNode<K,V>> nextGeneration = new ArrayList<>();
    List<PNode<K,V>> thisGeneration = new ArrayList<>();

    thisGeneration.addAll(this.children);

    // loop over one generation at a time
    while (thisGeneration.size() > 0) {

      // add all children in this generation
      for (PNode<K,V> child : thisGeneration)
        descendants.add(child);

      // ...then add all of THEIR children, from the next generation
      nextGeneration.clear();
      for (PNode<K,V> child : thisGeneration)
        nextGeneration.addAll(child.children);

      // ...then move from this generation to the next generation
      thisGeneration.clear();
      thisGeneration.addAll(nextGeneration);

    }

    return descendants;
  }

  // get all descendants in a particular generation (1 = children, 2 = grandchildren, etc.)
  public List<PNode<K,V>> getDescendantsByGeneration (int generation) {

    List<PNode<K,V>> descendants    = new ArrayList<>();
    List<PNode<K,V>> nextGeneration = new ArrayList<>();
    List<PNode<K,V>> thisGeneration = new ArrayList<>();
    List<Integer>    genNum         = new ArrayList<>();

    Integer currentGen = 1;

    thisGeneration.addAll(this.children);

    // loop over one generation at a time
    while (thisGeneration.size() > 0) {

      // add all children in this generation
      for (PNode<K,V> child : thisGeneration) {
        descendants.add(child);
        genNum.add(currentGen);
      } ++currentGen;

      // ...then add all of THEIR children to the next generation
      nextGeneration.clear();
      for (PNode<K,V> child : thisGeneration)
        nextGeneration.addAll(child.children);

      // ...then move from this generation to the next generation
      thisGeneration.clear();
      thisGeneration.addAll(nextGeneration);

    }

           // look through all of the descendants...
    return IntStream.range(0, descendants.size()).mapToObj(ii ->

           // pair the descendants with their generation indices...
           new SimpleEntry<Integer, PNode<K,V>>(genNum.get(ii), descendants.get(ii))).

           // only accept descendants from the desired generation...
           filter(pair -> pair.getKey() == generation).map(pair -> pair.getValue()).

           // and return them as a list
           collect(Collectors.toList());
  }

  public List<PNode<K,V>> getLeaves() {

    List<PNode<K,V>> leaves         = new ArrayList<>();
    List<PNode<K,V>> nextGeneration = new ArrayList<>();
    List<PNode<K,V>> thisGeneration = new ArrayList<>();

    thisGeneration.addAll(this.children);

    // similar to getDescendants(), but...
    while (thisGeneration.size() > 0) {

      // ...we only add children if they have no children themselves
      for (PNode<K,V> child : thisGeneration)
        if (child.isLeaf())
          leaves.add(child);

      // that's it!
      nextGeneration.clear();
      for (PNode<K,V> child : thisGeneration)
        nextGeneration.addAll(child.children);

      // everything else is the same
      thisGeneration.clear();
      thisGeneration.addAll(nextGeneration);

    }

    return leaves;
  }

  public List<PNode<K,V>> getAncestors() {

    List<PNode<K,V>> ancestors = new ArrayList<>();
    PNode<K,V> ancestor = this.parent;

    // only roots and leaves can be null
    while (ancestor != null) {
      ancestors.add(ancestor);
      ancestor = ancestor.parent;
    }

    return ancestors;
  }

  public PNode<K,V> getRoot() {
    PNode<K,V> ancestor = this;
    while (!ancestor.isRoot())
      ancestor = ancestor.parent;
    return ancestor;
  }

  ///---------------------------------------------------------------------------
  ///
  ///  other methods: isRoot, isLeaf, print tree, etc.
  ///
  ///---------------------------------------------------------------------------

  // returns true if this is a root node
  public boolean isRoot() { return (this.parent == null); }

  // returns true if this is a leaf node
  public boolean isLeaf() { return (this.children.size() == 0); }

  // print the tree with default arguments
  public void printTree() { printTree(0, 10, "", false); }

  // print the tree with desired number of levels above and below this node
  public void printTree(int nLevelsUp, int nLevelsDown) {
    if (nLevelsUp < 0 || nLevelsDown < 0) {
      System.err.println("nLevelsUp and nLevelsDown must both be >= 0");
      return;
    }

    System.out.println("");
    printTree(nLevelsUp, nLevelsDown, "", false);
  }

  // private method to print tree; some code here based on http://bit.ly/2HgFBRo
  private void printTree (int nLevelsUp, int nLevelsDown, String indent, boolean isTail) {

    // start with any node on the tree
    PNode<K,V> node = this;

    // find eldest allowed node using nLevelsUp
    for (int ii = 0; ii < nLevelsUp; ++ii) {
      if (node.parent != null) {
        node = node.parent;
        ++nLevelsDown;
      } else {
        --nLevelsUp;
      }
    }

    // get generation of eldest allowed node
    int gen = node.getAncestors().size();

    String treeLabel = (node == null ? "<null>" :
                 (node.label == null ? "<no label>" : node.label.toString()));

    // useless ternary operator left here in case formatting changes later
    System.out.printf("  %3d %s|-- %s%n", gen, indent, treeLabel);

    if(nLevelsDown > 0){
      for (int ii = 0; ii < children.size() - 1; ii++) {
        if (children.get(ii) == null) continue;
        children.get(ii).printTree(0, nLevelsDown-1, indent + (isTail ? "     " : "|    "), false);
      }

      if (children.size() > 0 && children.get(children.size()-1) != null) {
        children.get(children.size() - 1)
          .printTree(0, nLevelsDown-1, indent + (isTail ? "     " : "|    "), true);
      }
    }

    return;
  }

} // end class PNode


/*
  RESOURCES / CITATIONS:

  https://stackoverflow.com/questions/14649819/multilevel-map-in-java
  https://stackoverflow.com/questions/19330731/tree-implementation-in-java-root-parents-and-children
  https://stackoverflow.com/questions/3522454/java-tree-data-structure
  https://stackoverflow.com/questions/3642452/java-n-tuple-implementation
  http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/#comment-1461
*/

## PNode_Example.java
PNode<String, Integer> n01 = new PNode<>("n01_label", 123);
PNode<String, Integer> n02 = new PNode<>("n02_label", 234);
PNode<String, Integer> n03 = new PNode<>("n03_label", 345);
PNode<String, Integer> n04 = new PNode<>("n04_label", 456);
PNode<String, Integer> n05 = new PNode<>("n05_label", 567);
PNode<String, Integer> n06 = new PNode<>("n06_label", 678);
PNode<String, Integer> n07 = new PNode<>("n07_label", 789);
PNode<String, Integer> n08 = new PNode<>("n08_label", 890);

n01.addChildren(Arrays.asList(n02, n03))
n02.addChildren(Arrays.asList(n04, n05))
n03.addChildren(Arrays.asList(n06, n07))
n05.addChild(n08)

System.out.println("\n\nOriginal tree:\n");
n01.printTree()

n05.setParent(null)

System.out.println("\n\nTree after orphaning n05:\n");
n01.printTree()

System.out.println("\n\nn05 tree after orphaning n05:\n");
n05.printTree()

n05.setParent(n01)

System.out.println("\n\nTree after n01 adopts n05:\n");
n01.printTree()

/* SCRIPT OUTPUT

jshell> /open PNode.java
jshell> /open PNode_Example.java


Original tree:

    0 |-- n01_label
    1 |    |-- n02_label
    2 |    |    |-- n04_label
    2 |    |    |-- n05_label
    3 |    |         |-- n08_label
    1 |    |-- n03_label
    2 |         |-- n06_label
    2 |         |-- n07_label


Tree after orphaning n05:

    0 |-- n01_label
    1 |    |-- n02_label
    2 |    |    |-- n04_label
    1 |    |-- n03_label
    2 |         |-- n06_label
    2 |         |-- n07_label


n05 tree after orphaning n05:

    0 |-- n05_label
    1 |    |-- n08_label


Tree after adopting n05:

    0 |-- n01_label
    1 |    |-- n02_label
    2 |    |    |-- n04_label
    1 |    |-- n03_label
    2 |    |    |-- n06_label
    2 |    |    |-- n07_label
    1 |    |-- n05_label
    2 |         |-- n08_label

*/
	import java.util.AbstractMap.SimpleEntry;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Optional;
	import java.util.stream.Collectors;
	import java.util.stream.IntStream;


	public class PNode <K,V> {

	//----------------------------------------------------------------------------
	//
	// Think of nodes like a family tree...
	//
	// - each node has a value associated with it (knowledge of something)
	// - value can be null ("I don't know")
	// - two nodes (people) can have the same or different knowledge (values)
	//
	// - each node has a label (name)
	// - two nodes with the same parent can have the same name (why not?)
	// - labels can be null (old ancestor whose name is unknown)
	//
	// - value and label can BOTH be null, actually
	// - children are indexed, so we can refer to them by indices, at least
	//
	// - also, value and label can be identical among siblings
	// - (think: twins born to the same parents with the same names)
	// - just have to "index" them based on time of birth
	//
	// - when a child is removed (deceased), its index is not freed
	// - will always be "the first child" etc. of its parent
	// - child node set to null to maintain node indexing
	//
	//----------------------------------------------------------------------------

	public K label = null; // nodes have labels for easy searching within tree
	public V value = null; // value and label can both be null, because...

	// children of a node are held in a List, so nodes are indexed
	private List<PNode<K,V>> children = new ArrayList<>();
	private PNode<K,V> parent = null;

	///---------------------------------------------------------------------------
	///
	/// constructors
	///
	///---------------------------------------------------------------------------

	// create a root node (with no parent)
	public PNode(K label, V value) {
	this.label = label;
	this.value = value;
	// parent remains null
	// children List begins empty
	}

	// create a child node
	public PNode(K label, V value, PNode<K,V> parent) {
	this.label = label;
	this.value = value;
	this.parent = parent;
	parent.children.add(this);
	}

	///---------------------------------------------------------------------------
	///
	/// methods to add children to, or remove children from, this node
	///
	///---------------------------------------------------------------------------

	// add child with label and value to children
	public PNode<K,V> addChild (K label, V value) {
	return addChild(new PNode<K,V>(label, value));
	}

	// add a single child
	public PNode<K,V> addChild (PNode<K,V> child) {
	if (child != null)
	child.setParent(this);
	return child;
	}

	// add multiple children at once
	public void addChildren (Collection<PNode<K,V>> children) {
	if (children == null \|\| children.size() == 0) return;
	for (PNode<K,V> child : children)
	addChild(child);
	}

	// remove a single child
	public PNode<K,V> removeChild (PNode<K,V> child) {
	if (child == null) return null;
	int index = childIndex(child);
	if (index >= 0) {
	child.parent = null;
	this.children.set(index, null);
	} return child;
	}

	// remove multiple children at once
	public void removeChildren (Collection<PNode<K,V>> children) {
	if (children == null \|\| children.size() == 0) return;
	for (PNode<K,V> child : children)
	removeChild(child);
	}

	///---------------------------------------------------------------------------
	///
	/// methods to change or remove this node's parent
	///
	///---------------------------------------------------------------------------

	// set the parent of this node
	public boolean setParent (PNode<K,V> parent) {

	// if parent = null, call removeParent()
	if (parent == null) return removeParent();

	// if this is already the parent, do nothing
	if (parent.equals(this.parent)) return false;

	// otherwise, set new parent
	if (this.parent != null)
	this.parent.removeChild(this);
	this.parent = parent;
	parent.children.add(this);

	return true;
	}

	// remove this node's parents (make it a root node)
	public boolean removeParent() {

	// if null parent, return false
	if (this.parent == null) return false;

	// otherwise, remove this node's parent
	// and remove this child from the parent's children (set to null)
	PNode<K,V> retval = this.parent.removeChild(this);
	return (retval == null) ? false : true;

	}

	///---------------------------------------------------------------------------
	///
	/// methods to get this node's parent and child(ren)
	///
	///---------------------------------------------------------------------------

	// get the index of this exact child
	public int childIndex (PNode<K,V> child) {
	return children.indexOf(child);
	}

	// get all children of this node
	public List<PNode<K,V>> getChildren() {
	return Collections.unmodifiableList(children);
	}

	// get the parent of this node
	public PNode<K,V> getParent() { return parent; }

	///---------------------------------------------------------------------------
	///
	/// methods to get more distant relatives: descendants, leaves, roots, etc.
	///
	///---------------------------------------------------------------------------

	// get every node that descends from this node
	public List<PNode<K,V>> getDescendants() {

	List<PNode<K,V>> descendants = new ArrayList<>();
	List<PNode<K,V>> nextGeneration = new ArrayList<>();
	List<PNode<K,V>> thisGeneration = new ArrayList<>();

	thisGeneration.addAll(this.children);

	// loop over one generation at a time
	while (thisGeneration.size() > 0) {

	// add all children in this generation
	for (PNode<K,V> child : thisGeneration)
	descendants.add(child);

	// ...then add all of THEIR children, from the next generation
	nextGeneration.clear();
	for (PNode<K,V> child : thisGeneration)
	nextGeneration.addAll(child.children);

	// ...then move from this generation to the next generation
	thisGeneration.clear();
	thisGeneration.addAll(nextGeneration);

	}

	return descendants;
	}

	// get all descendants in a particular generation (1 = children, 2 = grandchildren, etc.)
	public List<PNode<K,V>> getDescendantsByGeneration (int generation) {

	List<PNode<K,V>> descendants = new ArrayList<>();
	List<PNode<K,V>> nextGeneration = new ArrayList<>();
	List<PNode<K,V>> thisGeneration = new ArrayList<>();
	List<Integer> genNum = new ArrayList<>();

	Integer currentGen = 1;

	thisGeneration.addAll(this.children);

	// loop over one generation at a time
	while (thisGeneration.size() > 0) {

	// add all children in this generation
	for (PNode<K,V> child : thisGeneration) {
	descendants.add(child);
	genNum.add(currentGen);
	} ++currentGen;

	// ...then add all of THEIR children to the next generation
	nextGeneration.clear();
	for (PNode<K,V> child : thisGeneration)
	nextGeneration.addAll(child.children);

	// ...then move from this generation to the next generation
	thisGeneration.clear();
	thisGeneration.addAll(nextGeneration);

	}

	// look through all of the descendants...
	return IntStream.range(0, descendants.size()).mapToObj(ii ->

	// pair the descendants with their generation indices...
	new SimpleEntry<Integer, PNode<K,V>>(genNum.get(ii), descendants.get(ii))).

	// only accept descendants from the desired generation...
	filter(pair -> pair.getKey() == generation).map(pair -> pair.getValue()).

	// and return them as a list
	collect(Collectors.toList());
	}

	public List<PNode<K,V>> getLeaves() {

	List<PNode<K,V>> leaves = new ArrayList<>();
	List<PNode<K,V>> nextGeneration = new ArrayList<>();
	List<PNode<K,V>> thisGeneration = new ArrayList<>();

	thisGeneration.addAll(this.children);

	// similar to getDescendants(), but...
	while (thisGeneration.size() > 0) {

	// ...we only add children if they have no children themselves
	for (PNode<K,V> child : thisGeneration)
	if (child.isLeaf())
	leaves.add(child);

	// that's it!
	nextGeneration.clear();
	for (PNode<K,V> child : thisGeneration)
	nextGeneration.addAll(child.children);

	// everything else is the same
	thisGeneration.clear();
	thisGeneration.addAll(nextGeneration);

	}

	return leaves;
	}

	public List<PNode<K,V>> getAncestors() {

	List<PNode<K,V>> ancestors = new ArrayList<>();
	PNode<K,V> ancestor = this.parent;

	// only roots and leaves can be null
	while (ancestor != null) {
	ancestors.add(ancestor);
	ancestor = ancestor.parent;
	}

	return ancestors;
	}

	public PNode<K,V> getRoot() {
	PNode<K,V> ancestor = this;
	while (!ancestor.isRoot())
	ancestor = ancestor.parent;
	return ancestor;
	}

	///---------------------------------------------------------------------------
	///
	/// other methods: isRoot, isLeaf, print tree, etc.
	///
	///---------------------------------------------------------------------------

	// returns true if this is a root node
	public boolean isRoot() { return (this.parent == null); }

	// returns true if this is a leaf node
	public boolean isLeaf() { return (this.children.size() == 0); }

	// print the tree with default arguments
	public void printTree() { printTree(0, 10, "", false); }

	// print the tree with desired number of levels above and below this node
	public void printTree(int nLevelsUp, int nLevelsDown) {
	if (nLevelsUp < 0 \|\| nLevelsDown < 0) {
	System.err.println("nLevelsUp and nLevelsDown must both be >= 0");
	return;
	}

	System.out.println("");
	printTree(nLevelsUp, nLevelsDown, "", false);
	}

	// private method to print tree; some code here based on http://bit.ly/2HgFBRo
	private void printTree (int nLevelsUp, int nLevelsDown, String indent, boolean isTail) {

	// start with any node on the tree
	PNode<K,V> node = this;

	// find eldest allowed node using nLevelsUp
	for (int ii = 0; ii < nLevelsUp; ++ii) {
	if (node.parent != null) {
	node = node.parent;
	++nLevelsDown;
	} else {
	--nLevelsUp;
	}
	}

	// get generation of eldest allowed node
	int gen = node.getAncestors().size();

	String treeLabel = (node == null ? "<null>" :
	(node.label == null ? "<no label>" : node.label.toString()));

	// useless ternary operator left here in case formatting changes later
	System.out.printf(" %3d %s\|-- %s%n", gen, indent, treeLabel);

	if(nLevelsDown > 0){
	for (int ii = 0; ii < children.size() - 1; ii++) {
	if (children.get(ii) == null) continue;
	children.get(ii).printTree(0, nLevelsDown-1, indent + (isTail ? " " : "\| "), false);
	}

	if (children.size() > 0 && children.get(children.size()-1) != null) {
	children.get(children.size() - 1)
	.printTree(0, nLevelsDown-1, indent + (isTail ? " " : "\| "), true);
	}
	}

	return;
	}

	} // end class PNode



	/*
	RESOURCES / CITATIONS:

	https://stackoverflow.com/questions/14649819/multilevel-map-in-java
	https://stackoverflow.com/questions/19330731/tree-implementation-in-java-root-parents-and-children
	https://stackoverflow.com/questions/3522454/java-tree-data-structure
	https://stackoverflow.com/questions/3642452/java-n-tuple-implementation
	http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/#comment-1461
	*/
	PNode<String, Integer> n01 = new PNode<>("n01_label", 123);
	PNode<String, Integer> n02 = new PNode<>("n02_label", 234);
	PNode<String, Integer> n03 = new PNode<>("n03_label", 345);
	PNode<String, Integer> n04 = new PNode<>("n04_label", 456);
	PNode<String, Integer> n05 = new PNode<>("n05_label", 567);
	PNode<String, Integer> n06 = new PNode<>("n06_label", 678);
	PNode<String, Integer> n07 = new PNode<>("n07_label", 789);
	PNode<String, Integer> n08 = new PNode<>("n08_label", 890);

	n01.addChildren(Arrays.asList(n02, n03))
	n02.addChildren(Arrays.asList(n04, n05))
	n03.addChildren(Arrays.asList(n06, n07))
	n05.addChild(n08)

	System.out.println("\n\nOriginal tree:\n");
	n01.printTree()

	n05.setParent(null)

	System.out.println("\n\nTree after orphaning n05:\n");
	n01.printTree()

	System.out.println("\n\nn05 tree after orphaning n05:\n");
	n05.printTree()

	n05.setParent(n01)

	System.out.println("\n\nTree after n01 adopts n05:\n");
	n01.printTree()

	/* SCRIPT OUTPUT

	jshell> /open PNode.java
	jshell> /open PNode_Example.java


	Original tree:

	0 \|-- n01_label
	1 \| \|-- n02_label
	2 \| \| \|-- n04_label
	2 \| \| \|-- n05_label
	3 \| \| \|-- n08_label
	1 \| \|-- n03_label
	2 \| \|-- n06_label
	2 \| \|-- n07_label


	Tree after orphaning n05:

	0 \|-- n01_label
	1 \| \|-- n02_label
	2 \| \| \|-- n04_label
	1 \| \|-- n03_label
	2 \| \|-- n06_label
	2 \| \|-- n07_label


	n05 tree after orphaning n05:

	0 \|-- n05_label
	1 \| \|-- n08_label


	Tree after adopting n05:

	0 \|-- n01_label
	1 \| \|-- n02_label
	2 \| \| \|-- n04_label
	1 \| \|-- n03_label
	2 \| \| \|-- n06_label
	2 \| \| \|-- n07_label
	1 \| \|-- n05_label
	2 \| \|-- n08_label

	*/