Interview Questions on Tree Data Structure (C Language)

A hierarchical data structure with nodes connected by edges, where each node has a parent and zero or more children.

Using a structure with data and pointers to child nodes (for binary trees, left and right pointers).

Binary trees restrict each node to at most two children (left and right).

In-order, pre-order, post-order (DFS), and level-order (BFS) traversals.

The number of edges on the longest path from root to a leaf node.

Number of edges from the node to the tree's root.

A node with no children.

A binary tree where left subtree contains only nodes with values less than the parent, and right subtree contains greater values.

Search/Insert/Delete: O(h) where h is tree height (O(log n) for balanced trees).

A tree where all levels are completely filled except possibly the last, which is filled left to right.

A tree where all interior nodes have exactly two children and all leaves are at the same level.

Trees are acyclic connected graphs with exactly one path between any two nodes.

A self-balancing BST where heights of left and right subtrees differ by at most 1.

An operation to change the structure of a tree while preserving the BST property, used in balancing.

Using arrays where indices represent parent-child relationships (heap implementation).

2^l nodes (for level 0 being the root).

A tree where null pointers are replaced with threads to other nodes for efficient traversal.

Faster search (O(log n)) compared to O(n) in arrays/lists when balanced.

Three cases: node with no children (simple delete), one child (replace with child), two children (replace with inorder successor/predecessor).

A tree-like structure for storing strings where each node represents a character prefix.

A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

B-trees can have more than two children per node and are optimized for disk storage systems.

A complete binary tree where parent nodes satisfy heap property (min-heap or max-heap).

Using an array of child pointers or a linked list of children in each node.

O(h) where h is tree height (O(log n) if balanced), found by traversing leftmost path.

The longest path between any two nodes in the tree.

A self-adjusting BST where recently accessed elements are moved to the root for faster access.

A tree data structure for storing intervals or segments, useful for range queries.

A data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Allows in-order traversal without recursion or stack, saving memory.

Perform in-order traversal and verify sequence is sorted, or recursively check BST property at each node.

O(n) for all traversals as each node is visited exactly once.

Using rotations (AVL) or restructuring operations (Red-Black trees).

A self-balancing BST with color properties on nodes ensuring O(log n) operations.

For BST: use BST properties. For general trees: use parent pointers or recursive search.

B+ trees store data only in leaf nodes and have linked leaves for sequential access.

Convert to string representation (e.g., pre-order with markers for null nodes).

An in-order traversal that uses threading to avoid recursion/stack (O(1) space).

Use max-heap for max-priority queue or min-heap for min-priority queue.

O(n) using bottom-up heap construction.

In-order traversal until k elements are visited (O(k) time).

Minimizes disk I/O by having high branching factor and storing multiple keys per node.

Use the property that size = 2^h+1-1 for perfect trees, adjust for complete trees.

O(n) using depth-first search.

Using a structure with child pointers (array or linked list) and an end-of-word marker.

Efficient for string operations like pattern matching, longest common substring, etc.

Recursive approach calculating local and global maximum sums.

A binary tree derived from a sequence that is heap-ordered and maintains sequence order.

File systems, databases, compilers (syntax trees), networking (routing trees), AI (decision trees).

Based on operations needed: BST for search, AVL/RB for guaranteed balance, B-tree for disk storage, etc.