Trees

Question 1

What is a tree in data structures?

Answer 1

A hierarchical data structure consisting of nodes, with one root node and subtrees of children.

Question 2

What is a binary tree?

Answer 2

A tree where each node has at most two children.

Question 3

What is a binary search tree (BST)?

Answer 3

A binary tree where left child < parent < right child for all nodes.

Question 4

What is a root node?

Answer 4

The topmost node in a tree.

Question 5

What is a leaf node?

Answer 5

A node with no children.

Question 6

What is an internal node?

Answer 6

A node with at least one child.

Question 7

What is the depth of a node?

Answer 7

The number of edges from the root to the node.

Question 8

What is the height of a node?

Answer 8

The number of edges on the longest downward path to a leaf.

Question 9

What is the height of a tree?

Answer 9

The height of the root node.

Question 10

What is a balanced binary tree?

Answer 10

A tree where the height difference between left and right subtrees is no more than 1.

Question 11

What is a complete binary tree?

Answer 11

All levels are fully filled except possibly the last, which is filled left to right.

Question 12

What is a full binary tree?

Answer 12

A binary tree where every node has either 0 or 2 children.

Question 13

What is a perfect binary tree?

Answer 13

A complete binary tree in which all leaf nodes are at the same level.

Question 14

What are the types of tree traversal?

Answer 14

Preorder, inorder, postorder, and level order.

Question 15

What is preorder traversal?

Answer 15

Visit the root, then left subtree, then right subtree.

Question 16

What is inorder traversal?

Answer 16

Visit the left subtree, then root, then right subtree.

Question 17

What is postorder traversal?

Answer 17

Visit the left subtree, then right subtree, then root.

Question 18

What is level order traversal?

Answer 18

Visit nodes level by level from top to bottom.

Question 19

What is the time complexity of traversing a tree?

Answer 19

O(n), where n is the number of nodes.

Question 20

What is a degenerate (or pathological) tree?

Answer 20

A tree where each parent has only one child, like a linked list.

Question 21

What is the average time complexity for search in a BST?

Answer 21

O(log n) for balanced trees.

Question 22

What is the worst-case time complexity for search in a BST?

Answer 22

O(n), when the tree is unbalanced.

Question 23

What is a self-balancing binary search tree?

Answer 23

A BST that maintains a balanced structure automatically (e.g., AVL, Red-Black Tree).

Question 24

What is an AVL tree?

Answer 24

A self-balancing BST where the balance factor of any node is -1, 0, or 1.

Question 25

What is a Red-Black Tree?

Answer 25

A self-balancing BST where each node is red or black, maintaining balance through color rules.

Question 26

What is the benefit of self-balancing trees?

Answer 26

They provide guaranteed O(log n) search, insert, and delete.

Question 27

How do you insert into a binary search tree?

Answer 27

Recursively or iteratively find the correct spot and add the node.

Question 28

How do you delete a node in a BST?

Answer 28

Handle three cases: no child, one child, two children (replace with in-order successor).

Question 29

What is an in-order successor?

Answer 29

The smallest node in the right subtree.

Question 30

What is an in-order predecessor?

Answer 30

The largest node in the left subtree.

Question 31

What is a trie?

Answer 31

A tree used for storing strings where each node represents a prefix.

Question 32

What is a n-ary tree?

Answer 32

A tree where nodes can have up to n children.

Question 33

What is a subtree?

Answer 33

A tree consisting of a node and all its descendants.

Question 34

What is the space complexity of a binary tree with n nodes?

Answer 34

O(n)

Question 35

How do you calculate the number of nodes in a perfect binary tree of height h?

Answer 35

2^(h+1) - 1

Question 36

What is the time complexity for insertion in a BST?

Answer 36

O(log n) for balanced trees, O(n) for unbalanced.

Question 37

What is the benefit of inorder traversal in a BST?

Answer 37

It returns the elements in sorted order.

Question 38

What is a threaded binary tree?

Answer 38

A tree where null pointers are used to point to in-order predecessors or successors.

Question 39

What is a binary expression tree?

Answer 39

A binary tree where leaves are operands and internal nodes are operators.

Question 40

What is the use of a tree in file systems?

Answer 40

Directory structures are often represented as trees.

Question 41

How do you check if two trees are identical?

Answer 41

Compare the data and structure recursively.

Question 42

What is a mirror of a binary tree?

Answer 42

A tree with left and right children swapped at all nodes.

Question 43

What is a segment tree?

Answer 43

A tree used for storing intervals and supporting efficient range queries.

Question 44

What is a binary indexed tree (Fenwick Tree)?

Answer 44

A tree-like structure used to perform prefix sum queries efficiently.

Question 45

What is the best-case time for searching in a balanced BST?

Answer 45

O(log n)

Question 46

What is the worst-case time for inserting into an unbalanced BST?

Answer 46

O(n)

Question 47

How is recursion commonly used with trees?

Answer 47

To traverse or modify tree nodes.

Question 48

What is a B-tree?

Answer 48

A self-balancing search tree optimized for systems that read and write large blocks of data.

Question 49

What is the main advantage of using a B-tree?

Answer 49

Efficient disk access and balanced search times.