DRAINER CS : Data Structures Final Review

Which of the following statements is true about Binary Search Trees (BSTs)?

• BSTs are not suitable for storing data in a sorted order

• The right subtree of a node in a BST contains values greater than the nodes value

• BSTs can never be unbalanced

• BSTs have a time complexity of O(n) for insertion and search operations

Which of the following operations can not be performed in O(log n) time in a perfect Binary Search Tree?

• Insertion

• Deletion

• Searching for a given key

• In-order traversal

What is the time complexity of finding the minimum value of a balanced Binary Search Tree

• O(n)

• O(1)

• O( log n)

• O(n log n)

Which of the following statements is true about the following code?

• The function prints the height of the tree

• The function prints the tree in post-order traversal

• The function prints the tree in in-order traversal

• The function prints the tree in pre-order traversal

Which of the following is not a property of Binary Search Trees

• A node can have at most two children.

• All nodes at the same level have the same value

• All nodes in the left subtree of a node have values less thatn the nodes valu

• All nodes in the right subtree of a node have values greater than the nodes value

Which of the following statements is true about the following python code?

• The function deletes the node with the given key from the tree

• The function inserts a new node with the given key in the tree

• The function searches for the node with the given key in the tree

• The function returns the minimum value in the tree

What could be the worst-case time complexity of inserting a node in a Binary Search Tree?

• O(log n)

• O(n log n)

• O(n)

• O(1)

Which of the following in an advantage of using a Binary Search Tree of an Array for storing data?

• Binary Search Trees can handle ordered data more effciently

• Arrays have better worst-case time complexity for search operations

• Binary Search Trees are more space efficient for small datasets

• Arrays can handle dynamic insertion and deletion of elements more efficiently

The following Python code attempts to insert a new node with the given key in a binary search tree. However, there is an error in the code that may cause the new node to be inserted in the wrong position, or not inserted at all. Which of the following options correctly identifies the cause of the error?

• The recursion calls for the method _insert() should start checking the right side of the tree

• if the BST tree is empty, the method insert() should create the root

• The method insert() should return None instead of a new node

• The method insert() is not receiving the root of the tree

Which of the following traversal options can be used to visit all of the nodes of a binary search tree in ascending order of their key values?

• pre-order traversal

• breadth-first traversal

• in-order traversal

• post-order traversal