Tree

Question 1

What is a tree?

Answer 1

A hierarchical data structure that simulates a tree-like structure with a set of connected nodes

Question 2

What is a binary tree?

Answer 2

A type of tree where each node can have at most two children

Question 3

What is a full tree?

Answer 3

A tree where every node has either zero children (leaf node) or two children. Also known as proper binary trees

Question 4

What is a complete tree?

Answer 4

A binary tree in which all levels are filled, except possibly the last level. The last level must strictly be filled from left to right. Data structures like Heap uses complete binary trees

Question 5

What is a balanced tree?

Answer 5

A binary tree where the difference in height between the left and right subtrees of any node in the tree is not more than 1. This ensures the tree remains reasonably balanced, preventing skewed structures

Question 6

What is a multi-way tree?

Answer 6

A type of tree that allows nodes to have more than two children

Question 7

What is a binary search tree (BST)?

Answer 7

A fundamental data structure that organizes elements in a hierarchical manner. Each node has at most two children and for any given node, all nodes in its left subtree have values less than or equal to the node’s value, and all nodes in its right subtree have values greater than the node’s value

Question 8

What is in-order traversal?

Answer 8

A type of binary search tree traversal that visits the left subtree, the current node, and then the right subtree, resulting in the elements being visited in ascending order

Question 9

What is pre-order traversal?

Answer 9

A type of binary search tree traversal that visits the current node, the left subtree, and the right subtree.

Question 10

What is a post-order traversal?

Answer 10

A type of binary search tree traversal that visits the left subtree, the right subtree, and then the current node.

Question 11

What is the time complexity of searching/insertion/deletion a balanced binary search tree (BST)?

Answer 11

O(log n)

Question 12

What is the time complexity of searching/insertion/deletion an unbalanced binary search tree (BST)?

Answer 12

O(n)

Question 13

What are issues with binary search trees?

Answer 13

1. Unbalanced: They can become unbalanced due to the order in which elements are inserted. If elements are inserted in a sorted order, they can turn into a linked list
2. Memory Overhead: Each node requires additional memory for storing pointers
3. Not suitable for dynamic datasets
4. Limited search performance for equal keys