addChild method for Binary Tree

Question

For a project, I have written my own Binary Tree class. I need to recursively build a left subtree and right subtree, so I have added a makeBinaryTreeNode method that takes in the root, the left Child, and the right Child. Inside of that I know I need to call some kind of method called, addChild after creating two leftChild and rightChild trees holding the data for the children, but I have no idea how you write an addChild method for a Binary Tree implementation. I've looked at other implementations where the children are stored in a list of nodes (Java tree data-structure? <-- the top answer in this thread used a list to store children nodes), but is there a better way to write an addChild method for a Binary Tree in java? Any help is appreciated!

score 0 · Accepted Answer · answered Dec 02 '15 at 07:09

0

//each tree is also a node
public class BinaryTree<T> extends Node<T>{
  private BinaryTree<T> parentNode;
  private BinaryTree<T> leftNode;
  private BinaryTree<T> rightNode;

  public BinaryTree() {

  }
}

public class Node<T> {

  T value;
}

answered Dec 02 '15 at 07:09

Roger Dwan

740
4
6

score 0 · Answer 2 · answered Dec 02 '15 at 07:10

this depends on the kind of binary tree, most binary trees have some kind of balancing to prevent trees which would have suboptimal lookup times. if you do not have to do balancing then theire are multiple ways of adding a child to a Node.

One Example would be: Having two kinds of Nodes first Leaf Nodes with no childs, second Inner Nodes with two childs. now writting a addChild could look the following:

on Leaf Nodes:

public Node addChild(Node n){
   return new InnerNode(this,n);  //without balancing new InnerNode(n,this); is fine to
}

on Inner Nodes:

public Node addChild(Node n){ 
   left = left.addChild(n); //without balancing right = right.addChild(n); is fine to
   return this;
}

But without balancing this is pointless and always degenerate to some kind of linked list.

One simple balancing would be to count the leaf nodes in a Branch. for LeafNode this is 1, for InnerNode this is sum of leaf nodes in left+right. then you could add the new node always to the side with less leafes.

But their are way better balancing technics for example in Red-Black trees.

addChild method for Binary Tree

2 Answers2