Binary Search trees Flashcards
What is a Binary Search Tree (BST)?
A Binary Search Tree is a data structure that maintains sorted order, where each node has at most two children, and for every node, the left child’s value is less than the node’s value, and the right child’s value is greater.
True or False: In a BST, duplicate values are allowed.
False
What is the time complexity for searching an element in a balanced BST?
O(log n)
Fill in the blank: The left subtree of a node in a BST contains only values that are _______ than the node’s value.
less
What is the main advantage of using a Binary Search Tree?
It allows for efficient searching, insertion, and deletion operations.
Which traversal method would you use to retrieve values from a BST in sorted order?
In-order traversal
True or False: The height of a BST can be as large as n in the worst case.
True
What is the average time complexity for insertion in a balanced BST?
O(log n)
What happens if you attempt to insert a duplicate value in a BST?
It can either be ignored or handled based on the implementation.
True or False: A BST can be used to implement a priority queue.
False
What is the space complexity of a BST?
O(n)
What is the maximum number of nodes in a complete binary tree of height h?
2^(h+1) - 1
What is a balanced BST?
A balanced BST is a tree where the height of the left and right subtrees of any node differ by at most one.
What is the worst-case time complexity for searching in an unbalanced BST?
O(n)
Fill in the blank: The _______ of a node is defined as the number of edges on the longest path from that node to a leaf.
height
What is the purpose of rotations in a BST?
To maintain balance in self-balancing BSTs like AVL trees.
True or False: A BST can be implemented using arrays.
True
What is the maximum depth of a BST with n nodes?
n in the worst case, O(log n) in the best case.
What is the primary characteristic that differentiates a BST from a regular binary tree?
The ordering property based on node values.
Fill in the blank: In a BST, the right subtree of a node contains only values that are _______ than the node’s value.
greater
What does the inorder traversal of a BST produce?
A sorted list of values.
What is the main disadvantage of a BST?
It can become unbalanced, leading to degraded performance.
True or False: A Binary Search Tree can be modified to allow duplicate values.
True
What is the role of the root node in a BST?
It serves as the starting point for all search operations.
