A tree is a non-linear data structure. It means you cannot access an element of tree in a straightforward manner.In this lesson, you learn about tree basics. This will serve as a foundation for future topics on trees. You can start learn about other topics if familiar with basics.
Informal definition of Tree
A tree is a set of one or more nodes with a special node called a Root node. Every none points to a left node and a right node. Sometimes left, right or both are missing and a node points to nothing.
Every node is part of some smaller set of nodes called a Sub-tree. Each sub-tree has more sub-trees.
Tree basics – Directed vs Undirected Tree
In an undirected tree, the edge between two nodes has no direction associated with it. However, a directed tree has some important properties
- The directed tree is acyclic means there is loop between the nodes.
- The directed tree is digraph means it is like a graph with direction. Each node has associated edges. If the node pointed by some other node, it is called an In-degree and if the node is pointing to some other node, its called an Out-degree.
- Root node has in-degree 0 and all other nodes have in-degree of 1.
- The minimum number of node allowed in a directed tree is 1. So, an isolated node is a directed tree.
In the above figure, 5 , 6 , 7, 8, 9 are leaf nodes.
In the above figure, 2, 3 and 4 are branch nodes.
Level of a Tree
Tree basics – Ordered Tree
In the above figure the Tree A and Tree B are same tree, but ordered differently.
The node 2 from tree B has a degree of 2 because node 4 and node 3 are its children.
The Concept of Forest
Descendant & Children of a Node
E.Balaguruswamy. 2013. Data Structures Using C. McGraw Hill Education.
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.