Trees and Graphs

Question 1

Graph

Answer 1

• node-based data structure
• a series of nodes that each may or may not have child nodes. These nodes may direct to each other in a circular fashion, and they may be bi-directional

Question 2

Breath first search (BFS)

Answer 2

-visits every neighbor of a node before visiting its children

Question 3

Depth first search (DFS)

Answer 3

• search each complete branch before moving to the next one

- covers searches through every available child node before moving to a neighbor

Question 4

Recursive

Answer 4

calls itself with new data until its done

Question 5

Trees

Answer 5

• a subtype of graph
• cannot contain cycles
• nodes without children are called “leaf nodes”
• may be restricted to n children per node, like a Binary Tree (n=2)

Question 6

Binary search tree

Answer 6

• a sorted binary tree
• left hand children are less or equal to root node and right hand children are greater than that node
• searching happens in O(logn) time

Question 7

Balanced vs Complete Tree vs Full

Answer 7

• balanced when the number of nodes to either side of the root are roughly equal
• complete when every non-leaf node has two children (except the rightmost node)
• full where every Level has exactly 0 or 2 children
• perfect tree is both full and complete

Question 8

Tree Traversal

Answer 8

• Inorder
• preorder
• post-order