Chapter 8

Question 1

Tree

Answer 1

A structure with a unique starting node (the root), in which each node is capable of having multiple child nodes, and in which a unique path exists from the root to every other node

Question 2

Root

Answer 2

The top node of a tree structure; a node with no parent

Question 3

Binary tree

Answer 3

A tree in which each node is capable of having two child nodes: a left child node and a right child node

Question 4

Leaf

Answer 4

A tree node that has no children

Question 5

Descendant

Answer 5

A child of a node, or a child of a parent

Question 6

Ancestor

Answer 6

A parent of a node, or a parent of an ancestor

Question 7

Binary search tree

Answer 7

A binary tree in which the value in any node is greater than or equal to the value in its left child and any of its descendants (the nodes in the left subtree) and less than the value in its right child and any of its descendants (the nodes in the right subtree)

Question 8

Preorder traversal

Answer 8

A systematic way of visiting all the nodes in a binary tree by visiting a node, then visiting the nodes in the left subtree of the node, and then visiting the nodes in the right subtree of the node

Question 9

Inorder traversal

Answer 9

A systematic way of visiting all the nodes in a binary tree by visiting the nodes in the left subtree of a node, then visiting the node, and then visiting the nodes in the right subtree of the node

Question 10

Postorder traversal

Answer 10

A systematic way of visiting all the nodes in a binary tree by visiting the nodes in the left subtree of a node, then visiting the nodes in the right subtree of the node, and then visiting the node

Question 11

Full binary tree

Answer 11

A binary tree in which all of the leaves are on the same level and every nonleaf node has two children

Question 12

Complete binary tree

Answer 12

A binary tree that is either full or full through the next-to-last level, with the leaves on the last level as far to the left as possible

Question 13

A structure with a unique starting node (the root), in which each node is capable of having multiple child nodes, and in which a unique path exists from the root to every other node

Answer 13

Tree

Question 14

The top node of a tree structure; a node with no parent

Answer 14

Root

Question 15

A tree in which each node is capable of having two child nodes: a left child node and a right child node

Answer 15

Binary tree

Question 16

A tree node that has no children

Answer 16

Leaf

Question 17

A child of a node, or a child of a parent

Answer 17

Descendant

Question 18

A parent of a node, or a parent of an ancestor

Answer 18

Ancestor

Question 19

A binary tree in which the value in any node is greater than or equal to the value in its left child and any of its descendants (the nodes in the left subtree) and less than the value in its right child and any of its descendants (the nodes in the right subtree)

Answer 19

Binary search tree

Question 20

A systematic way of visiting all the nodes in a binary tree by visiting a node, then visiting the nodes in the left subtree of the node, and then visiting the nodes in the right subtree of the node

Answer 20

Preorder traversal

Question 21

A systematic way of visiting all the nodes in a binary tree by visiting the nodes in the left subtree of a node, then visiting the node, and then visiting the nodes in the right subtree of the node

Answer 21

Inorder traversal

Question 22

A systematic way of visiting all the nodes in a binary tree by visiting the nodes in the left subtree of a node, then visiting the nodes in the right subtree of the node, and then visiting the node

Answer 22

Postorder traversal

Question 23

A binary tree in which all of the leaves are on the same level and every nonleaf node has two children

Answer 23

Full binary tree

Question 24

A binary tree that is either full or full through the next-to-last level, with the leaves on the last level as far to the left as possible

Answer 24

Complete binary tree