WELCOME LEARNERS Unacademy, because learning is priceless INDIA'S LARGEST LEARNING PLATFORM u n academy
ABOUT ME top educator 2017 My Name is SWETA KUMARI . Completed B.TECH IN COMPUTER SCIENCE. Verified & Unacademy PLUS Educator. .Presented Research Paper in NCCCS .Got Selected in 2 IT Companies. Hobbies: Like Playing Different Games, Comedy Shows & Obviously Teaching. Accolades: Top Educator at Unacademy unacademy FOLLOW ME FOLLhttps:/unacademy.com/user/hellosonu0
TARGET GATE CSE 2019 DATA STRUCTURES TREE, RED-BLACK TREE & AVL TREE 12 GATE PYQ's 20 30 10 40 1.0 40
MOTIVATION Positive thinking is not about expecting the best to happen, it's about accepting that whatever happens, happens for the best.
DS WEIGHTAGE Section 1: Engineering Mathematics (14-20 Marks) Section 2: Digital Logic Section 11: General Aptitude (3 -6 Marks) Section 3: Computer Organization and Architecture (5-7 Marks) Section 4: Programming and Data Structures (10 15 Marks) Section 5: Algorithms (5-7 Marks) Section 6: Theory of Computation (8-10 Marks) Section 7: Compiler Design (15 Marks) (4 -6 Marks) Section 8: Operating System (8- 10 Marks) Section 9: Databases (5-7 Marks) Section 10: Computer Networks (8-11 Marks)
GENERAL APTITUDE ENGINEERING MATHEMATICS PROGRAMMING AND DATA STRUCTURES COMPUTER NETWORKS OPERATING SYSTEM 5 THEORY OF COMPUTATION COMPUTER ORGANIZATION AND ARCHITECTURE ALGORITHMS DATABASES COMPILER DESIGN DIGITAL LOGICn
TOPIC WISE WEIGHTAGE Total 19 Questions have been asked from Tree topic of Data Structures subject in previous GATE papers. Average marks 1.
TARGET GATE CSE 2019 6 MONTH STRATEGY PLAN unacadenny
Third Month: SUB TOPIC Probability: Random variables. Uniform, normal, exponential, poisson and binomial distributions. Mean, median, mode and standard deviation. Conditional probability and Bayes theorem DAY SUBJECT TOPIC DAY 1 Probability Engineering Mathematics Databases File organization, indexing (e.g., B and B+ File organization, indexing (e.g., B and B+ trees) trees) DAY 2 DAY 3 Computer Network IPV6/IPV4 IPv4/IPv6, routers and routing algorithms (distance vector, link state) Graph search Instruction pipelining DAY 4 Graph search Algorithms Computer Organization and DAY 5 Instruction pipelining Architecture Programming and Data Structures Theory of Computation DAY 6 Programming in C Binary search trees Turing machines and undecidability DAY 7 Turing machines and undecidability
Third Month: DAY DAY 8 DAY 9 SUB TOPIC File systems syntax-directed translation SUBJECT TOPIC File systems syntax-directed translation Operating System Compiler Design DAY 10Programming and Programming in C. Trees Data Structures DAY 11 Operating System DAY 12Computer Network Process & Threads Deadlock Network security authentication, basics of public key and private key cryptography, digital signatures and certificates, firewalls DAY 13 Databases Transactions and concurrency control ICG Minimum spanning trees Transactions and concurrency control DAY 14Compiler Design DAY 15 Algorithms Intermediate Code Generation Minimum spanning trees,
CONCEPT COURSE https://unacademy.com/lesson/course-overview-in-hindi/1V4DV6TJ (Hindi) Tree: Data Structures and Programming For GATE EXAM (12) Sweta Kumari (Hindi) Data Structures : Tree Traversals Related Problems for... Sweta Kumari o academy
GATE Question Which of the following is a true about Binary Trees (A) Every binary tree is either complete or full. (B) Every complete binary tree is also a full binary tree. (C) Every full binary tree is also a complete binary tree. (D) No binary tree is both complete and full. (E) None of the above
B) is incorrect. The following binary tree is complete but not full 12 20 30 30 12 C) is incorrect. Following Binary tree is full, but not complete 20 30 20 40
Note that nodes are unlabeled. If the nodes are labeled, we get more number of trees.
(GATE CS 2005) Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? (A) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95 (B) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29 (C) 29,15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95 (D) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Answer (A) Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.
GATE Question Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree? (A) (1 2 (4 5 6 7)) (B) (1 (2 3 4) 5 6) 7) (C) (1 (2 34)(5 6 7)) (D) (1 (2 3 NULL) (4 5))
GATE Question Consider a node X in a Binary Tree. Given that X has two children, let Y be Inorder successor of X. Which of the following is true about Y'? (A) Y has no right child (B) Y has no left child (C) Y has both children (D) None of the above
Answer (B) Since X has both children, Y must be leftmost node in right child of X.
sum of all degrees = 2 * 1 El. Here considering tree as a k-ary tree: Sum of degrees of leaves Sum of degrees for Internal Node except root + Root's degree = 2 * (No. of nodes-1). Putting values of above terms, L + (1-1)*(k+1) + k = 2 * (L + 1-1) L+k*l-k+1-1+k=2*L+21-2 ANSWER (B) K* l + 1-1=L (KI) + 1-L Given k = 2, L=20 ==> (2-1)*1 + 1 = 20 I19 >T has 19 internal nodes which are having two children.
.The number of different binary trees with 6 nodes is fact(2n)/ fact(n+1) * fac(n) where n is no nodes: If n 6, then fact (2 * n) / fact(n+1)* fac(n) ANSWER (C) fact(2 * 6) / fact(6 + 1) * fact(6) fact(12) / fact(7) * fact(6) 12 11* 10 * 9 * 8* fact(7) fact(7) * fact(6) 12 11 10 * 9*8/6*5 *4 3 * 2 6 * 11 2 132
ISRO CS 2013 Which of the following number of nodes can form a full binary tree? (A) 8 (B) 15 (C) 14 (D) 13
Answer (B) A full binary tree is a binary tree in which all nodes except leaves have two children. In a Full Binary, number of leaf nodes is number of internal nodes plus 1 L=1+1 .Where L Num ber of leaf nodes, l = Number of internal nodes
ISRO CS 2009 A full binary tree with n leaves contains: (A) n nodes (B) log2 n nodes (C) 2n-1 (D) 2"
ISRO CS 2008 A complete binary tree with the property that the value at each node is as least as large as the values at its children is known as (A) binary search tree (B) AVL tree (C) completely balanced tree (D) Heap
Answer (D) In a Max. Binary Heap, the key value at each node is as least as large as the values at its children. Similarly in Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap.
YouTuber (channel : GATE NoteBook) | Verified Educator | 2+ year Online Teaching Experience