Graphs

Question 1

Binary Search Tree (BST)

Answer 1

A binary search tree is a data structure consisting of nodes, each holding a value and pointers to its left and right children. Nodes on the left side of the tree have values less than the root’s value, while those on the right have greater values.

Question 2

Operations on Binary Search Trees

Answer 2

1. Insertion: Adding a new node with a specific value to the binary search tree while maintaining its properties.
2. Deletion: Removing a node with a specific value from the binary search tree while maintaining its properties.
3. Search: Finding a node with a specific value in the binary search tree.
4. Traversal: Visiting all nodes of the binary search tree in a specific order (inorder, preorder, postorder).

Question 3

Time complexity for binary search trees

Answer 3

1. The average-case time complexity for insertion, deletion, and search operations in a balanced binary search tree is O(log n), with ‘n’ representing the number of nodes.
2. In a worst-case scenario, where the binary search tree is unbalanced, the time complexity for insertion, deletion, and search operations may deteriorate to O(n), with ‘n’ being the number of nodes.