Tree Nodes

Question 1

A leaf node is a node…

Answer 1

that has no children

Question 2

True or False.
Any node with a child is an internal node

Answer 2

True

Question 3

How many children can a node have in a binary tree?

Answer 3

It can have up to 2 children

Question 4

What is the depth of a root node?

Answer 4

0

Question 5

If a tree has just one node what is the depth?

Answer 5

0

Question 6

A link from a node to a child is called a…

Answer 6

edge

Question 7

A binary tree is full if…

Answer 7

Every node contains 0 or 2 children

Question 8

A binary tree is perfect if…

Answer 8

All internal nodes have 2 children and all leaf nodes are at the same level

Question 9

A binary tree is complete if…

Answer 9

All levels, except the last level, contain all possible nodes and all nodes in the last level are as far left possible

Question 10

What is a binary search tree?

Answer 10

Orders the left child of the less than or equal to the parent node
Orders the right child greater than or equal to the parent node

Question 11

Where does searching begin in a tree?

Answer 11

It begins at the root

Question 12

Example: If you are searching for 145 in a tree and the root of the node is 300, where will the search begin?

Answer 12

145< 300, so the search will begin with the left child

Question 13

If a match is not found what is returned?

Answer 13

Null

Question 14

Insert as a node as a left child involves…

Answer 14

If the new node is less than the current node
The current nodes left child is null

Question 15

Insert a node as a right child involves…

Answer 15

If the new node’s key is greater than or equal to the current node
The current node right child is null

Question 16

Searching for an insert location involves…

Answer 16

If the right or left child is not null
The algorithm assigns the current node with that child and continues looking for a proper location

Question 17

What is a tree traversal?

Answer 17

Visits all the nodes in the tree and performs an operation on each node

Question 18

What is an inorder traversal?

Answer 18

Visits all the nodes in a BST from smallest to largest

Question 19

What is the algorithm for in order traversal?

Answer 19

left current right

Question 20

What is the height of a tree?

Answer 20

Is the maximum number of edges from the root of the tree

Question 21

If a tree’s height is N=7, what is the height?

Answer 21

h - 1 = 7 - 1 = 6
Therefore the answer is 6.

Question 22

How can you implement a search using recursion?

Answer 22

A base case is checking if the node is not null
If the key is equal to the node
If the key is less than
node–> key return

Question 23

What is a preorder traversal?

Answer 23

Starts at the root node than works its way down the left side of child then the right side
Moves on to the right side of the tree and goes through the left children than the right children

Question 24

What is inorder traversal?

Answer 24

Starts on the left subtree than the root node then moves on to the right subtree

Question 25

What is post order traversal?

Answer 25

Starts on the left subtree than the right sub tree and then the root node

Question 26

What does the find(key) method do?

Answer 26

Returns the reference to node containing key if present

Question 27

What does the findMin() do?

Answer 27

Returns the node containing the smallest key

Question 28

What does the findMax() do?

Answer 28

Returns the node containing the largest key

Question 29

What does add(key) do?

Answer 29

Inserts a new node in tree at correct position(unless already present)

Question 30

What does remove(key) do?

Answer 30

Removes key from tree if present