Answer Key
University
California State UniversityCourse
COMP 182 | Data Structures and Program Design and LabPages
12
Academic year
2022
NyiH
Views
30
How many children does a binary tree have? 2 any number of children 0 or 1 or 2 0 or 1.
What are the children for node 'w' of a complete-binary tree in an array representation? 2w and 2w+1 2+w and 2-w w+1/2 and w/2 w-1/2 and w+1/2
If the tree is not a complete binary tree then what changes can be made for easy access of children of a node in the array? every node stores data saying which of its children exist in the array no need of any changes continue with 2w and 2w+1, if node is at i keep a seperate table telling children of a node use another array parallel to the array with tree
Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed? Yes just traverse through the array and form the tree No we need one more traversal to form a tree No in case of sparse trees Yes by using both inorder and array elements
A binary tree is a rooted tree but not an ordered tree true false binary tree is a rooted tree but not an ordered tree binary tree is a rooted tree but not an ordered tree, Question 6 How many common operations are performed in a binary tree? 1 2 3 4
What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes) O(1) O(nlogd) O(logd)
In a full binary tree if number of internal nodes is I, then number of leaves L are? L =2*I L = I + 1 L = l - 1 L=2* I - 1
What is a complete binary tree? Each node has exactly zero or two children A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right A tree In which all nodes have degree 2
The number of edges from the root to the node is called ___ of the tree Height Depth Length Width
Using what formula can a parent node be located in an array? (i+1)/2 (i-1)/2 i/2 2i/2
If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?2i+1 2i+2 2i 4i
How many orders of traversal are applicable to a binary tree (In General)? 1 4 2 3
How many types of insertion are performed in a binary tree? 1 2 3
What is the traversal strategy used in the binary tree? depth-first traversal breadth-first traversal random traversal Priority traversal
Binary Tree Basics: Understanding Children Count
Please or to post comments