iterators recursion trees Flashcards
What is the purpose of the Iterator interface?
To access data items in a collection one at a time, where each element is delivered exactly once
What are the three main operations provided by an Iterator?
hasNext(), next(), and remove() (optional)
What is recursion in programming?
A programming technique where a method calls itself to solve a problem by breaking it into smaller identical problems
What is the difference between linear and non-linear recursion?
Linear recursion makes only a single recursive call each time the function runs, while non-linear recursion makes multiple recursive calls
What are the two essential components of a recursive method?
- Base case(s) that provide non-recursive solutions for simple inputs 2. Recursive calls that make progress toward the base case
What is tail recursion?
When there is only one recursive call at the very end of a method, with no deferred operations building up
What is a tree data structure?
A non-linear ADT that stores information in a hierarchy, consisting of nodes connected by edges
What is the difference between a leaf node and an internal node?
A leaf node has no children, while an internal node has at least one child
What is the height of a tree?
The length of the longest path from the root to a leaf
What are the four common tree traversal methods?
- 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)
What is a Binary Search Tree (BST)?
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
What makes a tree ‘balanced’?
All leaves of the tree are on the same level or within one level of each other
What is a degenerate tree?
An unbalanced tree where most nodes have at most one child, essentially degrading into a linked list
What are the three main steps in recursive problem-solving?
- Break the problem into smaller problems 2. Solve until reaching a known simple solution 3. Build the complete solution from smaller pieces
What is the time complexity of Binary Search?
O(log n)
What determines the shape of a Binary Search Tree?
The order in which elements are added to the tree
What is an expression tree?
A binary tree that represents an arithmetic expression where internal nodes contain operations and leaf nodes contain operands
What is indirect recursion?
When two or more methods call each other in a cycle (e.g., Method A calls Method B, which calls Method A)
What is the level of a node in a tree?
The number of edges between the root and the node
What is the order we follow for Pre-Order traversal?
visit root first, traverse subtrees left to right.
What is the order we follow for In-Order traversal?
traverse left subtree, then visit root, then traverse right subtree.
What is the order we follow for Post-Order traversal?
traverse subtrees from left to right, then visit the root.
What is the order we follow for Level Order traversal?
visit each node at each level of the tree from top (root) to bottom, left to right.
