Observe the pictures given below:
The first picture is a family tree, the second one shows the student council system of a school and the third one represents the company pecking order.
What is common in all the pictures is the way that the data is represented: in a hierarchical manner. The data structure which is used to represent data in a hierarchical manner is known as Tree. Tree in computer science is like a tree in the real world, the only difference is that in computer science it is visualized as upside-down with root on the top and branches originating from the root to the leaves of the tree.
In Technical language: A tree is a non linear data structure in which each node can point to more than one node and as stated above a tree data structure stores data in a hierarchical manner
Glossary:
1. Root: The root of a tree is the node with no parents (Node A). There can be a maximum of one root node
2. Edge: link from parent to child
3. Leaf: a node with no child (Nodes D,H,F,G)
4. Siblings: Children nodes of the same parent node (B,C) (D, E and F)
5. Ancestor: a node say ‘p’ is an ancestor of node say ‘q’ if there exists a path from root to p and q. ( Nodes A, B, E are ancestors of H)
6. Depth of a node: is the length of the path from the root to the node (depth of node G is 2, A-C-G)
7. Height of a node: length of path from that node to the deepest node. ( height of B is 2, B-E-H)
8. Level: set of all nodes at a given depth. (node A is at level 0, nodes B,C are at level 1, Nodes D,E,F,G are at level 2, Node H is at level 3)
9. Height/Depth of tree: length of path from root to the deepest node. A (rooted) tree with only one node (the root) has a height of zero
Different types of Trees include:
1. General tree
2. Binary Tree
3. Binary Search Tree
4. AVL Tree
5. Red- Black Tree
6. N-ary Tree
(these will be discussed in coming up posts so stay tuned!)
References:
1. Data Structures and Algorithms made easy in Java (by Narasimha Karumanchi)
2. https://www.thecrazyprogrammer.com/
Happy Learning!!