Page 535 - Computer science 868 Class 12
P. 535
13.4 TREE
We have learnt about linear data structures like array, stack, A
queue, linked list where data is stored in a sequential manner.
Now we will know about a data structure where data is stored
in different levels similar to a family tree. B C
Tree is a non-linear data structure containing a collection
of interconnected nodes joined in a definite sequence. The
nodes are arranged in different levels depicting a hierarchical
relationship among itself. D E F G
13.4.1 Basic terminologies of a Tree
• Node: Each element of a tree is called a node. A node contains a value and a link to its next node.
• Root: The topmost node of a tree is called a root. The other nodes called sub nodes emerge from the root. There
can be only one root node of a tree.
• Parent or Predecessor node: The node from where sub nodes emerge is called a parent node. Thus a node with one
or more child nodes is a parent node.
• Child node: A node directly connected to another node as its immediate successor is called a child node. All nodes
except root node are child nodes.
• Leaf node: A node which does not have any child node is called a leaf or external node.
• Internal node or Branch node: All nodes excluding the root node and leaf nodes are called internal nodes.
• Edge: The connecting link of a node to its successor node is called an edge. A tree with ‘N’ nodes will have ‘N-1’
edges.
• Path: The sequence of edges joining one node with another node is called a path.
• Size: Total number of nodes in a tree is called its size.
• Sibling: Nodes belonging to same the parent node are called sibling.
• Sub tree: The set of nodes present on either side of a parent node is called sub tree. The left side nodes from left
sub tree while the right side nodes form right sub tree.
• Descendant: Any successor node on the path from the parent node to the child node is called descendant.
• Ancestor: Any predecessor node on the path from the child node to the parent node is called ancestor.
Let us understand the terms with the following tree given as an example.
• Each element of a tree is called a node. In this example, 8, 3, 10, 1, 6, 15,
13, 4, 7 are nodes. 8
• The root node is 8.
• The parent node of 6 is 3, 15 is 10 and so on. 3 10
• The child nodes of 6 are 4 and 7. Similarly, the child node of 15 is 13.
• The leaf nodes of this tree are 1, 4, 7, and 13.
• The internal nodes of the tree are 3, 10, 6, 15. 1 6 15
• The line joining 8 and 10 or 10 and 15 or 3 and 6 etc. is called an edge.
• The path from 8 to 7 are the edges connecting 8 with 3, 3 with 6 and 6
with 7. 4 7 13
• The size of the tree is 9.
533
Data Structures 533

