Trees & Hierarchical Structures

What is a Binary Tree?

A tree structure where each parent can have at most two children, allowing hierarchical organization of data.

What are the roles of nodes in a Binary Tree?

Nodes can be parent or child; the root is the topmost node; parents can have left and right children.

What are the three fields of a Binary Tree node?

Data element, pointer to left child, pointer to right child.

What are leaf nodes?

Nodes with no children; both child pointers are NULL.

Give an application of Binary Trees.

Used in databases to organize files into folders for easy searching.

What is Tree Traversal?

Visiting every node once in a specific order to access or process data.

How does tree traversal differ from linear structures?

Linear structures read data one way; trees can be traversed in multiple ways.

What are the two primary categories of tree traversal?

Breadth-First Traversal (BFT) and Depth-First Traversal (DFT).

What is Breadth-First Traversal?

Visits nodes level by level using a queue; useful in scheduling and shortest paths.

What is Depth-First Traversal?

Explores a branch as deeply as possible before backtracking.

What is Inorder Traversal?

Left → Root → Right; retrieves values in sorted order in BSTs.

What is Preorder Traversal?

Root → Left → Right; useful for copying trees or prefix expressions.

What is Postorder Traversal?

Left → Right → Root; useful for deleting trees or postfix expressions.

What is a Binary Search Tree (BST)?

An ordered binary tree where left < root < right, no duplicates, all keys unique.

What is the BST property of the right subtree?

All nodes in the right subtree must be greater than the parent.

What is the BST property of the left subtree?

All nodes in the left subtree must be less than the parent.

Does a BST allow duplicate nodes?

No, every key must be unique.

Why must every BST node have a unique key?

To keep search, insert, and delete operations efficient (O(log n)).

What is an AVL Tree?

A self-balancing BST where each node has a balance factor of -1, 0, or +1.

What is the balance factor in AVL Trees?

Difference in height between left and right subtrees.

What does a balance factor of +1, 0, -1 mean?

+1 = left taller, 0 = equal height, -1 = right taller.

What happens if AVL balance factor goes beyond -1 or +1?

The tree rebalances itself using rotations.

What is an LL Rotation?

Right rotation when insertion makes the left subtree of the left child too heavy.

What is an RR Rotation?

Left rotation when insertion makes the right subtree of the right child too heavy.

What is an LR Rotation?

Double rotation: Left rotate child, then Right rotate parent (zig-zag imbalance).

What is an RL Rotation?

Double rotation: Right rotate child, then Left rotate parent (zig-zag imbalance).

What is the application of trees in Hierarchical Data Representation?

Used in file systems, organizational charts, and DOM structures.

What is the application of trees in Searching and Sorting?

BSTs, AVL, and Red-Black Trees allow fast searching, inserting, and deleting.

What is the application of trees in Databases?

B-Trees/B+ Trees for indexing; Tries for autocomplete, dictionary, and IP routing.

What is the application of trees in Artificial Intelligence?

Decision Trees for ML, Minimax Trees for games, Behavior Trees for NPCs.

What is the application of trees in Compiler Design?

ASTs represent program structure; Parse Trees show grammatical structure.

What is the application of trees in Cryptography and Security?

Merkle Trees for blockchain verification; trees also for credential checks.

What is the application of trees in Networking?

Tries for fast IP lookups; MSTs optimize network designs by minimizing costs.