Perfect Tree, is Binary one !

Tree dictate how to organize data. It’s a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root.

The root node does not have a parent.

In Java class hierarchy the root is Object class.Every object in java JDK is extends from Object class.

For tree characteristics:

  • Every item in the tree is a node
  • The node at the top of the tree is the root
  • Every no-root node has one and only one parent
  • A leaf node has no children
  • A singleton tree has only one node which is the root
  • A path is a sequence of nodes required to go from one node to another.

Notably, we cannot cyclique paths,we cannot find a path that cross a node different times.

The Binary Tree,is the most important tree.It has this characteristics:

  • Every node has 0, 1, or 2 children
  • Children are referred to as left child and right child

In practice, we use binary search trees(BST).it can perform insertions, deletions, and retrievals in O(logn) time.

The left child always has a smaller value than its parent, and the right child has a larger value than its parent.This means everything to the left of the root is less than the value of the root, and everything to the right of the root is greater than the value of the root.Because of that, we can do binary search.

Importantly, binary search can be done in one of three levels (Traversal ways)

  • Level — visit nodes on each level
  • Pre-order — visit the root of every subtree first
  • Post-order visit the root of every subtree last

In-order level visit left child, then root, then right child. The data has to be sorted.

Moreover, for deleting node with two children:

  • Need to figure out what the replacement node will be
  • Want minimal disruption to the existing tree structure
  • Can take the replacement node from the deleted node’s left subtree or right subtree
  • If taking it from the right subtree, we have to take the smallest value in the right subtree
  • Choose one and stick to it

Example of Implementation:

  • TreeNode class is a Node class
  • Tree class is our custom tree implementation
  • Main class for testing :
  • The console output :

15,20,22,25,26,27,29,30,32,
data=30
null
15
32
Delete from the tree
15,20,22,25,26,27,29,30,

Conclusion:

As a conclusion, By searching in java JDK,to see what their is for trees,I found TreeMap class, is a binary search.

it’s implementation provides guaranteed log(n) time cost for containsKey,get, put and remove operations.

I am a software engineer and entrepreneur. My focus is on Developing technical skills,Learning marketing,and taking care of the health.