Trees and Graphs in Python - Interview Questions and Answers

A tree is a hierarchical data structure consisting of nodes, where each node has a value and a list of child nodes. It starts with a root node and branches out.

A binary tree is a type of tree where each node can have at most two children: left and right.

A BST is a binary tree in which the left subtree of a node contains values less than the node, and the right subtree contains values greater than the node.

A balanced binary tree is one where the height of the left and right subtrees of every node differ by at most one.

A complete binary tree is one in which all levels are completely filled except possibly the last, and all nodes are as far left as possible.

A full binary tree is a tree where every node has 0 or 2 children.

A perfect binary tree is one where all internal nodes have two children, and all leaf nodes are at the same level.

Traversal refers to visiting each node of a tree in a specific order: In-order, Pre-order, Post-order, or Level-order.

In in-order traversal, you visit the left subtree, then the root, then the right subtree.

In pre-order traversal, you visit the root first, then the left subtree, and finally the right subtree.

In post-order traversal, you visit the left subtree, then the right subtree, and finally the root.

Level-order traversal visits all nodes level by level using a queue (Breadth-First Search).

A graph is a collection of nodes (vertices) connected by edges. Graphs can be directed or undirected.

In a directed graph, edges have direction (A ➜ B). In undirected graphs, edges have no direction (A — B).

A cyclic graph is one that contains at least one cycle—a path where the start and end node are the same.

An acyclic graph has no cycles. A directed acyclic graph (DAG) is commonly used in scheduling and dependency graphs.

A graph where each edge has a numerical value (weight) representing cost, distance, or time.

It is a dictionary where each key is a vertex, and its value is a list of connected vertices.

A 2D matrix where rows and columns represent vertices, and the value indicates edge presence/weight.

DFS is a traversal algorithm that explores as far as possible down a branch before backtracking, typically implemented using recursion or a stack.

BFS is a graph traversal algorithm that explores all neighbors at the current depth before moving to nodes at the next depth level. It's usually implemented using a queue.

Use DFS with a visited and recursion stack (for directed graphs) or Union-Find (for undirected graphs).

A linear ordering of nodes in a directed acyclic graph (DAG) where for every directed edge u → v, u comes before v.

A shortest path algorithm for graphs with non-negative edge weights. It finds the shortest path from a source node to all other nodes.

DFS uses a stack and explores deep into the graph before backtracking. BFS uses a queue and explores nodes level by level.

It helps efficiently select the next node with the smallest cost, such as in Dijkstra’s algorithm.

A tree that connects all the vertices in a graph with the minimum possible total edge weight.

Both are algorithms to find the MST. Kruskal's uses edges sorted by weight; Prim’s grows the MST from a starting vertex.

Using dictionaries (adjacency list), sets, or lists for connections, optionally with edge weights.

A BST that automatically keeps its height small, such as AVL Tree or Red-Black Tree, to maintain performance.

A self-balancing BST where the balance factor of every node is maintained to be -1, 0, or 1.

A self-balancing BST where each node has a color and balance is maintained through color and rotations.

A tree-like data structure used to store strings, often used for autocomplete or prefix matching.

A binary tree used for storing intervals or segments, useful for range queries like sum or minimum.

A data structure that allows efficient prefix sum calculations and updates.

A tree where each node can have up to N children.

Leaf: no children. Internal: has at least one child. Root: the topmost node.

Height is the number of edges in the longest path from root to a leaf. Depth is the number of edges from the root to a node.

A graph with directed edges and no cycles, used in job scheduling, data pipelines, etc.

A tree is a type of graph with no cycles, one root, and connected nodes. A general graph can have cycles, disconnected components, and no hierarchy.

A binary tree is balanced if for every node, the difference in height between its left and right subtrees is at most 1. You can use a recursive function that returns height and checks balance.

• Full: Every node has 0 or 2 children.
• Complete: All levels are filled except possibly the last, which is filled left to right.
• Perfect: All levels are completely filled.

Convert the tree to a string using preorder traversal with placeholders for nulls (#) and reconstruct using recursion or a queue.

Traverse the tree recursively. If one node is found in the left subtree and the other in the right, the current node is the LCA.

A binary tree where null pointers are used to point to in-order predecessor or successor, improving traversal efficiency.

Use BFS or DFS to try coloring the graph with two colors. If a conflict is found, it's not bipartite.

Use an explicit stack instead of recursion. Push the starting node and loop while the stack is not empty.

An edge whose removal increases the number of connected components in the graph. Found using DFS and discovery times.

A node whose removal increases the number of connected components. Identified via DFS and low-link values.

An algorithm to find strongly connected components (SCCs) in a directed graph using DFS and a reversed graph.

An efficient method to find SCCs or articulation points in a graph using DFS and low-link values.

A shortest path algorithm that works with negative weights and can detect negative weight cycles.

Use the Bellman-Ford algorithm. If a distance can be reduced after |V|-1 iterations, there's a negative cycle.

A pathfinding algorithm that uses heuristics to prioritize nodes. Combines features of Dijkstra and greedy search.

Convert it into a linked list in-place following preorder traversal. Use recursion or a stack.

Swap the left and right children of all nodes, recursively or using BFS/DFS.

Average case: O(log n); Worst case (unbalanced): O(n)

• Adjacency matrix: 2D array for constant time edge checks; O(V²) space.
• Adjacency list: Dictionary or list of neighbors; efficient space for sparse graphs.

Traverse the tree recursively and count nodes with no children.

• Trees: File systems, expression parsing, autocompletion.
• Graphs: Social networks, road maps, web page link analysis, recommendation systems.