Tree – Abstract Data Type | MADE EASY
A Tree is a data structure similar to linked lists but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. Trees is an example of non-linear data structures.
It is a hierarchical data structure which stores the information naturally in the form of hierarchy style. In trees ADT (Abstract Data Type), order of the elements is not important. If we need ordering information linear data structures like linked lists, stacks, queues, etc. can be used.
- The root of a tree is the node with no parents. There can be at most one root node in a tree (node A in the above example).
- An edge refers to the link from parent to child (all links in the figure).
- A node with no children is called leaf node (E, J, K, H and I)
- Children of same parent are called siblings (B, C, D are siblings and children of A and E, F are the siblings and children of B).
- A node p is an ancestor of a node q if there exists a path from root to q and p appears on the path.
- The node q is called a descendant of p. For example, A, C and G are the ancestors for K.
- The depth of a node is the length of the path from the root to the node (depth of G is 2, A-C-G).
- The height of a node is the length of the path from the root to the node to the deepest node. The height of a tree is the length of a path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero. In the previous example, height of B is 2(B-F-J). Height of the tree is the maximum height among all the nodes in the tree and depth of the tree is the maximum depth among all the nodes in the tree. For a given tree depth and height returns the same value. But for individual nodes we may get different results.
- Size of a node is the number of descendants it has including itself (size of the subtree C is 3).
- Set of all nodes at a given depth is called level of the tree (B, C and D are same level). The root node is at level zero.
- If every node in a tree has only one child (except leaf nodes) then we call such trees as skew trees. If every node has only left child then we call them as left skew trees. Similarly, if every node has only right child then we call them as right skew trees.
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
