Data Structures and Algorithms Final
Exam Study Guide
Depth First Search - Answer- "think sink" Root node first
Visit Root -> visit left child -> repeat until no more left children -> visit sibling -> if
children visit those -> climb back up
Post-Order Traversal - Answer- Visit node after all children are visited
Root node last
Breadth First Search - Answer- Visit nodes top to Bottom, left to right like reading a
book
In-Order Traversal - Answer- Visit node after left child but before right
Must be BST
Complexity of traversing tree - Answer- Linear
Complexity of inserting into a tree - Answer- Logarithmic to Linear
Removing a Node from a BST - Answer- Replace node with smallest value from right
subtree
Splay Tree - Answer- a self-balancing binary tree that places recently accessed
elements near the top of the tree for fast access.
Zig Rotation - Answer- Parent is moved to become child of node (single rotation)
zig-zag rotation - Answer- If the node is left child of the parent which is right child of
grandparent, move grandchild up two levels and grandparent right child (double
rotation)
zig-zig rotation - Answer- If the node is the left child of the parent which is also the
left child of the grandparent, move up grandchild two levels by making parent right
child and grandparent right child of the parent (double rotation)
Time Complexity - Answer- the amount of time taken by an algorithm to run as a
function of the input size
Auxiliary Complexity - Answer- The amount of memory used by algorithm
Space Complexity - Answer- The total space taken by an algorithm with respect to
the input size
time complexity for stacks and queues - Answer- search: linear
insert/push: constant
remove/pop: constant
Exam Study Guide
Depth First Search - Answer- "think sink" Root node first
Visit Root -> visit left child -> repeat until no more left children -> visit sibling -> if
children visit those -> climb back up
Post-Order Traversal - Answer- Visit node after all children are visited
Root node last
Breadth First Search - Answer- Visit nodes top to Bottom, left to right like reading a
book
In-Order Traversal - Answer- Visit node after left child but before right
Must be BST
Complexity of traversing tree - Answer- Linear
Complexity of inserting into a tree - Answer- Logarithmic to Linear
Removing a Node from a BST - Answer- Replace node with smallest value from right
subtree
Splay Tree - Answer- a self-balancing binary tree that places recently accessed
elements near the top of the tree for fast access.
Zig Rotation - Answer- Parent is moved to become child of node (single rotation)
zig-zag rotation - Answer- If the node is left child of the parent which is right child of
grandparent, move grandchild up two levels and grandparent right child (double
rotation)
zig-zig rotation - Answer- If the node is the left child of the parent which is also the
left child of the grandparent, move up grandchild two levels by making parent right
child and grandparent right child of the parent (double rotation)
Time Complexity - Answer- the amount of time taken by an algorithm to run as a
function of the input size
Auxiliary Complexity - Answer- The amount of memory used by algorithm
Space Complexity - Answer- The total space taken by an algorithm with respect to
the input size
time complexity for stacks and queues - Answer- search: linear
insert/push: constant
remove/pop: constant
