iterators recursion trees

Question 1

What is the purpose of the Iterator interface?

Answer 1

To access data items in a collection one at a time, where each element is delivered exactly once

Question 2

What are the three main operations provided by an Iterator?

Answer 2

hasNext(), next(), and remove() (optional)

Question 3

What is recursion in programming?

Answer 3

A programming technique where a method calls itself to solve a problem by breaking it into smaller identical problems

Question 4

What is the difference between linear and non-linear recursion?

Answer 4

Linear recursion makes only a single recursive call each time the function runs, while non-linear recursion makes multiple recursive calls

Question 5

What are the two essential components of a recursive method?

Answer 5

1. Base case(s) that provide non-recursive solutions for simple inputs 2. Recursive calls that make progress toward the base case

Question 6

What is tail recursion?

Answer 6

When there is only one recursive call at the very end of a method, with no deferred operations building up

Question 7

What is a tree data structure?

Answer 7

A non-linear ADT that stores information in a hierarchy, consisting of nodes connected by edges

Question 8

What is the difference between a leaf node and an internal node?

Answer 8

A leaf node has no children, while an internal node has at least one child

Question 9

What is the height of a tree?

Answer 9

The length of the longest path from the root to a leaf

Question 10

What are the four common tree traversal methods?

Answer 10

1. Pre-Order (root, left, right) 2. In-Order (left, root, right) 3. Post-Order (left, right, root) 4. Level Order (level by level, left to right)

Question 11

What is a Binary Search Tree (BST)?

Answer 11

A binary tree where for each node: left subtree contains elements less than the node’s value, and right subtree contains elements greater than or equal to the node’s value

Question 12

What makes a tree ‘balanced’?

Answer 12

All leaves of the tree are on the same level or within one level of each other

Question 13

What is a degenerate tree?

Answer 13

An unbalanced tree where most nodes have at most one child, essentially degrading into a linked list

Question 14

What are the three main steps in recursive problem-solving?

Answer 14

1. Break the problem into smaller problems 2. Solve until reaching a known simple solution 3. Build the complete solution from smaller pieces

Question 15

What is the time complexity of Binary Search?

Answer 15

O(log n)

Question 16

What determines the shape of a Binary Search Tree?

Answer 16

The order in which elements are added to the tree

Question 17

What is an expression tree?

Answer 17

A binary tree that represents an arithmetic expression where internal nodes contain operations and leaf nodes contain operands

Question 18

What is indirect recursion?

Answer 18

When two or more methods call each other in a cycle (e.g., Method A calls Method B, which calls Method A)

Question 19

What is the level of a node in a tree?

Answer 19

The number of edges between the root and the node

Question 20

What is the order we follow for Pre-Order traversal?

Answer 20

visit root first, traverse subtrees left to right.

Question 21

What is the order we follow for In-Order traversal?

Answer 21

traverse left subtree, then visit root, then traverse right subtree.

Question 22

What is the order we follow for Post-Order traversal?

Answer 22

traverse subtrees from left to right, then visit the root.

Question 23

What is the order we follow for Level Order traversal?

Answer 23

visit each node at each level of the tree from top (root) to bottom, left to right.