Trees and Graphs Flashcards
What is a binary tree?
A hierarchical data structure where each node has at most two children.
What is a binary search tree (BST)?
A binary tree where the left child has smaller values and the right child has larger values.
What is a graph?
A set of nodes (vertices) connected by edges.
What is the difference between a directed and an undirected graph?
Directed graphs have edges with a direction, while undirected graphs have bidirectional edges.
What are common graph representations?
Adjacency Matrix (O(V²) space) and Adjacency List (O(V+E) space).
What is a full binary tree?
A binary tree where every node has either 0 or 2 children.
What is a complete binary tree?
A binary tree where all levels are completely filled except possibly the last, which is filled from left to right.
What is a balanced tree?
A tree where the height difference between left and right subtrees is minimal (e.g., AVL Tree).
What is an example of an application of graphs?
Google Maps (shortest path algorithm), social networks (friend connections).
