Tree Basics

A Tree data structure is a hierarchical collection of nodes. Each Tree node stores a data value and has pointers to pointing to its child nodes.

•	A single node at the topmost level is called the root node. 
•	Nodes that have children are called parent nodes. 
•	Nodes at lower levels (not lowest levels) are called branch nodes. 
•	Nodes at lowest level are called leaf nodes and do not have child nodes. 
•	Parent or child nodes of a node are called its neighbors.
•	The number of children of a tree is known as its Degree.
•	The max Degree of nodes in the Tree is known as the Degree of the Tree.

In the below diagram:

•	Node with data value 4 is the root node.
•	Nodes with data value 4, 5,7, 6, 14, 16, 18 are parent nodes and branch nodes.
•	Nodes with data values 33, 78, 8, 9 are leaf nodes.

Types of Trees

•	N-ary tree: Each node of N-ary Tree may have 0..n nodes.
•	Ternary tree: Each node of Ternary Tree may have 0..3 nodes.
•	Binary tree: Each node of Binary Tree may have 0..2 nodes.
•	Binary Search Tree: a Binary tree that’s nodes are sorted as per binary sort algorithm.
•	AVL tree :a self balancing binary tree.
•	Red-Black tree: a self balancing binary search tree with coloring rules.
•	B-Tree: A B-Tree of order n is node with maximum n children per parent.

Use cases for Trees

Algorithms requiring efficient sorting.

Algorithms requiring efficient searching.

To represent hierarchies, hierarchical data.

Used in databases for quick data access.

Used in compilers, Interpreters to parse expressions.

Time Complexity of Binary Search Tree operations

Following table shows time complexity metrics for BST Operations:

Operation	Complexity
Add operation.	O(log n)
Remove/Delete operation.	O(log n)
Search operation.	O(log n)
Traverse	O(n)

Tree in Java JDK API.

Java API does not provide a Binary Tree class, which provides the required Binary Tree behavior. Below code challenges provide a custom Binary Tree implementation.