Chapter 39 - Trees

Question 1

What does a rooted tree have?

Answer 1

» Has a root
» Branches
» Leaves

Question 2

What are the differences between a tree in computer science and real life?

Answer 2

» In computer science has its root at the top and its leaves at the bottom

Question 3

What are the typical uses for rooted trees?

Answer 3

» Manipulating hierarchial data
» Manipulated sorted lists of data
» Making information easy to search

Question 4

What is a tree?

Answer 4

» A tree is a fundamental data structure
» Consists of nodes and pointers

Question 5

What does each tree have?

Answer 5

» A root node

Question 6

What are the leaf nodes?

Answer 6

» Nodes at the very bottom of the tree
» And a node which has no children

Question 7

What are nodes connected with?

Answer 7

» Pointers also known as edges

Question 8

What is a subtree?

Answer 8

» A set of nodes and edges from any single node down through all of its descendants is known as a subtree

Question 9

What does each edge connect?

Answer 9

» 2 nodes
» Evert node except the root is connect by exactly one edge from another node

Question 10

What is the root?

Answer 10

» Only root which has no incoming edges

Question 11

What is the child ?

Answer 11

» The set of nodes that have incoming edges from the same node

Question 12

What is a binary tree?

Answer 12

» Similar to a standard rooted tree
» In which eah node has a maximum of 2 children

Question 13

What is a binary tree?

Answer 13

» Similar to a standard rooted tree
» In which eah node has a maximum of 2 children

Question 14

How can binary trees be represented in memory?

Answer 14

» As dicitonaries

Question 15

What are the values of the right pointer/ left pointer if there is no child node?

Answer 15

» Null

Question 16

What are the applications of binary trees?

Answer 16

» Database applications where efficient searching is required
» Wireless networking and routing tables

Question 17

What does each node in a binary tree contain?

Answer 17

» A left pointer
» A right pointer
» Data

Question 18

What are the steps to add an item to a binary tree?

Answer 18

» Check if there is free memory for the node - if there isn’t output an error
» Create a new node and insert data into it

Question 19

What happens if the binary tree is empty when data is being added to it?

Answer 19

» New node becomes first item - create a start pointer to it

Question 20

What happens if the binary tree is not empty, when trying to add an item to a binary tree?

Answer 20

» Start at root node
» If new node should be placed before the current node, follow the left pointer
» If new should be placed after the current node, follow the right pointer
» Repeat until the leaf node is reached
» Set right pointer of the previous node

Question 21

How can we find the item we want to delete from the binary tree?

Answer 21

» Start at the root node and set it as the current node
» While the current node exists and is not the one to be deleted:
» If item to be deleted is < than the current node, follow the left pointer, if > follow the right pointer

Question 22

What are the steps to remove an item from a binary tree if the node has no children?

Answer 22

» If the previous node is greater than the current node, previous node’s left pointer is set to null

» Else, the previous node’s right pointer is set to null

Question 23

What is the Hibbard deletion algorithm?

Answer 23

» To delete a node, we find the smallest value in the right sub-tree(Sucessor)
» And move it the position occupied by G
» Smalles value in the right - sub tree will always be left-most node in the right sub tree

Question 24

What are the problems with the Hibbard delete program?

Answer 24

» Tree may become unbalanced, as any node can become the root node.

Question 25

What are the problems of adding and deleting nodes?

Answer 25

» It can impact the efficiency algorithms on binary trees

Question 26

What are the steps to use hibbard deletion if the right node exists and it has no left sub tree?

Answer 26

» Set the current node to the node’s right pointer
» Set the current node’s pointer to null

Question 27

What is a simple alternative to delete nodes from a tree?

Answer 27

» Is to introduce another attribute to each node that flags it for delted
» These deleted nodes are skipped when traversing the tree

Question 28

What is a simple alternative to delete nodes from a tree?

Answer 28

» Is to introduce another attribute to each node that flags it for delted
» These deleted nodes are skipped when traversing the tree

Question 29

What is the problem of flagging?

Answer 29

» Increase space complexity

Question 30

What are the three different binary tree traversal methods that you need to be aware of?

Answer 30

» Pre-order
» In-order
» Post-order

Question 31

What is pre-order traversal?

Answer 31

» A variation of a depth-first search used to create a copy of a binary tree

Question 32

What are the steps of pre-order traversal?

Answer 32

» Start at root node
» Output node
» Traverse the left sub tree - Continue traversing through the left pointer, until there is no pointer to traverse
» Return to previously visted node and traverse the right sub-tree
» Returen the root node and traverse the right sub-tree

Question 33

What is in-order traversal?

Answer 33

» Variation of depth-first search to output the contents

Question 34

What is the signifcant advantage of in-order traversal?

Answer 34

» Automatically sorts the contents of the structure without moving data - negates the need for insertion sort

Question 35

What are the steps of in-order traversal?

Answer 35

» Traverse the left-sub tree
» Go as fat as possible along the left-sub tree
» Return from the point visting the other nodes
» Traverse as far as possible on the right-sub tree
» Return to the root visiting the root node

Question 36

How can you output nodes in reverse order?

Answer 36

» Simply reverse the algorithm by following the right pointer before outputting the node

Question 37

What is a good exam tip?

Answer 37

» Make sure you read the question carefully to check whether it ask for a right hand tree or a left hand treee

Question 38

What is prefix notation?

Answer 38

» Polish notation - Pre-order traversal

Question 39

What is infix notation?

Answer 39

» Inorder traversal

Question 40

What is postfix notation?

Answer 40

» Post order traversal
» Reverse polish notation

Question 41

What is post-order traversal?

Answer 41

Depth-first search to delete a binary tree

Question 42

What are the steps of a post-order traversal?

Answer 42

» Start at the root node
» Traverse left sub-tree
» Follow the left pointer until it is far down as possible
» Go as far as down on the left sub tree
» Return to root visiting node
» Traverse right sub-tree

Question 43

What is one key tip to remember in post-order traversal?

Answer 43

» Each markers are on the right hand side of each node

Question 44

What is the purpose of Reverse polish notation?

Answer 44

» To evaluate algebraic expressions

Question 45

What are the steps to add nodes to a binary tree?

Answer 45

» Start at root node
» If item is less, go left
» If item is more go right

Question 46

What is tree traversal?

Answer 46

» The process of visiting(checking or updating) each node in a tree data structure

Question 47

What are the benfits of a binary tree?

Answer 47

» Dynamic
» Printed out in a sequence
» Searched quickly