Page 540 - Computer science 868 Class 12
P. 540
Example 5: Answer the following from the given diagram of a Binary Tree. [ISC 2013]
(i) Preorder Transversal of the tree A
(ii) Children of node E
(iii) The left sub tree of node D
(iv) Height of the tree when the root of the tree is at level 0 I B
Ans. (i) Pre Order Traversal: A, I, B, C, D, E, G, H, F C D
(ii) Children of node E are G, H
(iii) Left sub tree of node D is E, G, H E F
(iv) Height of the tree taking root at level 0 is 4
G H
Let’s Revisit
♦ Data structure is a systematic way of storing and organizing data in a specialized format , and its relationship with all
associated members.
♦ In Linear data structure data elements are arranged contiguously one after another. The adjacent elements are attached with
one another and is traversed linearly. Example array, stack, queue etc.
♦ In Non linear data structure the data elements are arranged in a hierarchical order representing parent child relationship.
Example tree and graph
♦ In Static data structure the size and format is fixed during declaration.
♦ In Dynamic data structure we declare the element with an initial size, which can be changed during runtime as per requirement.
♦ A stack is a linear data structure which stores data in LIFO (Last In First Out) order. A stack has only one end , top. Insertion and
deletion of data takes place from the top only.
♦ A queue is a linear data structure which works on FIFO principle. It has two ends namely the front and the rear. Insertion in a
queue takes place from the rear end and deletion from the front end.
♦ A Double Ended Queue or Dequeue is a modified Queue where insertion and deletion are performed from both rear and front end
♦ Circular queue is a special type of queue where the front and rear ends are connected to form a circular structure. Circular
queue follows the queue principle of FIFO
♦ The linked list is a linear data structure . that contains a sequence of elements called “Node” which are linked to one another
by reference or memory address. Unlike array the nodes are not stored at contagious memory locations.
♦ 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.
♦ A binary tree is a tree structure where the degree is 2. A binary tree has maximum of two children.
♦ There are three types of tree traversals namely pre order. post order , in order
538538 Touchpad Computer Science-XII

