trees

Question 1

what do trees show

Answer 1

hiearachy

Question 2

Linear data structure

Answer 2

Array, list, stack queues
Elements are structured in one linear order

Question 3

Non linear(hierarchal) data structure

Answer 3

No natural order for elements
Tree and graph

Question 4

how many edges in tree

Answer 4

Tree has N nodes and N-1 edges because edge connects to its parent

Question 5

External node(leaf)

Answer 5

No children

Question 6

Internal node

Answer 6

At least one child

Question 7

path

Answer 7

sequence of nodes such that n1 is parent of n1+1 and so on

Question 8

path length

Answer 8

number of edges on path

Question 9

what does each node have

Answer 9

has a data element, parent node pointer and pointers to children nodes

Question 10

BST operations

Answer 10

Initize new tree
Bool is empty
search(private)- return pointer to node in which key is found, other wise return null ptr
search(public)-return true is key is found
Find min
Find maz
Insert - done at leaf
Remove
display

Question 11

BST array implemantation pro and con

Answer 11

Pro - easy implementation and fast access
Con - mostly suitable for complete trees

Question 12

tree preorder traversal

Answer 12

node is visited before its descendants
List the node the first time its passed

Question 13

what pass does tree in preorder listing list a node

Answer 13

second pass

Question 14

what pass does tree in postorder listing list a node

Answer 14

last pass

Question 15

five possible situations for BST deletiong

Answer 15

-ittem not found
-removing leaf
-removing node with one chilg - left
-removing node with one child - right
-

Question 16

removing node with one child

Answer 16

nodes parent next is nodes child
if root, root = nodes child

Question 17

removing node with two chidren

Answer 17

Successor- replace node information with smallest value larger than value to remove
Predecessor - replace node information with largest value smaller than value to remove