Tree Data Structure

We have all watched trees from our childhood. It has roots, stems, branches and leaves. It was observed long back that each leaf of a tree can be traced to root via a unique path. Hence tree structure was used to explain hierarchical relationships, e.g. family tree, animal kingdom classification, etc.

This hierarchical structure of trees is used in Computer science as an abstract data type for various applications like data storage, search and sort algorithms.

A tree is a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges. A tree has the following properties:

  1. The tree has one node called root. The tree originates from this, and hence it does not have any parent.
  2. Each node has one parent only but can have multiple children.
  3. Each node is connected to its children via edge.
Terminology

1.Root is a special node in a tree. The entire tree originates from it. It does not have a parent.
2.Parent node is an immediate predecessor of a node.
3.All immediate successors of a node are its children.
4.Node which does not have any child is called as leaf.
5.Edge is a connection between one node to another. It is a line between two nodes or a node and a leaf.
6.Nodes with the same parent are called Siblings.
7.Path is a number of successive edges from source node to destination node.
8.Height of a node represents the number of edges on the longest path between that node and a leaf.
9.Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
10.Degree of a node represents the number of children of a node.







































Types of Tree

General Tree: A tree in which there is no restriction on the number of children a node has, is called a General tree. Examples are Family tree, Folder Structure.

Binary Tree: In a Binary tree, every node can have at most 2 children, left and right.  

Binary trees are further divided into many types based on its application. 

  • Full Binary Tree: If every node in a tree has either 0 or 2 children, then the tree is called a full tree. The tree in the above diagram is not a full binary tree as node C has only the right child.
  • Perfect Binary tree: It is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.


Tree in-order traversal gives elements in sorted array.








Comments

Post a Comment

Popular posts from this blog

Java 8 : Find the number starts with 1 from a list of integers

  List<Integer> list = List. of ( 12 , 32 , 14 , 15 , 56 ); //Result->12,14,15 List<String> listString = list.stream().map(String::valueOf).collect(Collectors.toList()); List<String> result1 = listString.stream().filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result1-->" +result1); List<String> result2 = list.stream().map(x->x+ "" ).filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result2-->" +result2);
Read more

Junit Mockito and Power Mockito

Mock vs Spy Both can be used to mock methods or fields. The difference is that  in mock, you are creating a complete mock or fake object while in spy, there is the real object and you just spying or stubbing specific methods of it . Mock vs InjectMock @Mock  creates a mock.  @InjectMocks  creates an instance of the class and injects the mocks that are created with the  @Mock  (or  @Spy ) annotations into this instance. Unit Testing Void Methods with Mockito and JUnit How to Test Void Methods  As we already know that our aim is to test void methods in a class. But it is also really important to understand why we test void methods.  Whenever we write unit test cases for any method, we expect a return value from the method. Generally, we use assert for checking if the method returns the value that we expect it to return, but in the case of void methods, they do not return any value. So how do we check if our method is functioning properly? Let’s...
Read more

Customized Immutable Class

Image
Java Immutable Class In Java, when we create an object of an immutable class, we cannot change its value. For example, String is an immutable class. Hence, we cannot change the content of a string once created. Besides, we can also create our own custom immutable classes. Here's what we need to do to create an immutable class. declare the class as final so it cannot be extended all class members should be private so they cannot be accessed outside of class shouldn't contain any setter methods to change the value of class members the getter method should return the copy of class members class members are only initialized using constructor. PROS - Immutable Object is Threadsafe. For Constant Value. Used as a HashMap Key. (String, Integer, all wrapper classes are immutable) Why Hashmap key should be immutable? Immutability allows you to get same hash code every time, for a key object. So it actually solves most of the problems in one go. Also, this class must honor the hashCode() ...
Read more