Tree basics

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

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!)

1. Data Structures and Algorithms made easy in Java (by Narasimha Karumanchi)

Happy Learning!!

Leave a Reply


Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: