Tree
2 min readNov 17, 2021
A tree is non-linear and a hierarchical data structure consisting of a collection of nodes such that each node of the tree stores a value, a list of references to nodes.
Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical data structures.
- All nodes should be connected
- There should be no cycles
Basic Terminologies
- Root — The topmost node is called root of the tree. The node which doesn’t have a parent node.
- Children — The elements that are directly under an element are called its children.
- Parent — The element directly above something is called its parent.
- Leaf Node / External Node — A node that has no child nodes.
- Non-Leaf Node / Internal Node — A node that has child nodes.
- Path — Sequence of consecutive edges from the source node to the destination node.
- Ancestor — Any predecessor (previous) node on the path from the root to that node.
- Descendant — Any successor (after) node on the path from that node to leaf node.
- Sibling — Children of the same parent.
- Degree of Node — The no of children of that node.
- Degree of Tree — Max degree among all nodes.
- Depth of Node — Length of the path from the root to that node.
- Height of Node — No of edges in the longest path from that node to a leaf.
- Height of Tree — Height of root node.
- Level of Node — Depth of that node.
- Level of Tree — Height of tree.
- Diameter — The number of nodes on the longest path between two end nodes.
- Neighbour: Parent or child nodes of that node are called neighbours of that node.
- Subtree: Any node of the tree along with its descendants.
Implementation
class Node
{
int value;
Node left, right;
public Node(int data)
{
value = data;
left = right = null;
}
}Thanks
