DS&A Interview Questions Flashcards
What is a Binary Search Tree?
Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
What is an Inorder BST traversal?
Inorder traversal: In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. We visit the left child first, then the root, and then the right child.
What is a Preorder BST traversal?
Preorder traversal: Preorder traversal first visits the root node and then traverses the left and the right subtree. It is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions on of an expression tree.
What is a Postorder BST traversal?
Postorder traversal: Postorder traversal first traverses the left and the right subtree and then visits the root node. It is used to delete the tree. In simple words, visit the root of every subtree last.
What is a Level Order Traversal?
Level order traversal: Level order traversal of a BST is breadth first traversal for the tree. It visits all nodes at a particular level first before moving to the next level.
What are the 4 basic operations of BST?
The four basic operations of BST:
Searching,
Insertion, and
Deletion
Traversals
How does searching a BST work?
1Searching in a BST:
Searching in BST involves the comparison of the key values. If the key value is equal to root key then, search successful, if lesser than root key then search the key in the left subtree and if the key is greater than root key then search the key in the right subtree.
Searching in BST algorithm:-
Check if tree is NULL, if the tree is not NULL then follow the following steps.
Compare the key to be searched with the root of the BST.
If the key is lesser than the root then search in the left subtree.
If the key is greater than the root then search in the right subtree.
If the key is equal to root then, return and print search successful.
Repeat step 3, 4 or 5 for the obtained subtree.
How does insertion in a BST work?
Insertion in a BST:
Insertion in BST involves the comparison of the key values. If the key value is lesser than or equal to root key then go to left subtree, find an empty space following to the search algorithm and insert the data and if the key is greater than root key then go to right subtree, find an empty space following to the search algorithm and insert the data.
How does deletion in a BST work?
Deletion in BST involves three cases:-
First, search the key to be deleted using searching algorithm and find the node. Then, find the number of children of the node to be deleted.
Case 1- If the node to be deleted is leaf node: If the node to be deleted is a leaf node, then delete it.
Case 2- If the node to be deleted has one child: If the node to be deleted has one child then, delete the node and place the child of the node at the position of the deleted node.
Case 3- If the node to be deleted has two children: If the node to be deleted has two children then, find the inorder successor or inorder predecessor of the node according to the nearest capable value of the node to be deleted. Delete the inorder successor or predecessor using the above cases. Replace the node with the inorder successor or predecessor.
What are the 4 types of traversals in a BST?
- Traversals in a BST:
There are 4 types of traversals of the Binary Search Tree.
Level Order Traversal: Each node of the tree is traversed level by level in order of its appearance.
Pre-order Traversal: The nodes are traversed in the format of root and then left subtree and then right subtree.
Inorder Traversal: The nodes are traversed in the format of left subtree and then root and then right subtree.
Post Traversal: The nodes are traversed in the format of left subtree and then right subtree and then root
What are some ways Binary Search Trees are used?
Applications of Binary Search tree:
(real world)
BSTs are used for indexing in databases.
It is used to implement searching algorithms.
BSTs are used to implement Huffman coding algorithm.
It is also used to implement dictionaries.
Used for data caching.
Used in Priority queues.
Used in spell checkers.
(in general)
BSTs are used for indexing.
It is also used to implement various searching algorithms.
IT can be used to implement various data structures.
BSTs can be used in decision support systems to store and quickly retrieve data.
BSTs can be used to store and quickly retrieve data in computer simulations.
BSTs can be used to implement fast autocomplete systems.
BSTs can be used to implement decision trees, which are used in machine learning and artificial intelligence to model decisions and predict outcomes. Decision trees are used in many applications, including medical diagnosis, financial analysis, and marketing research.
BSTs can be used in encryption algorithms such as RSA, which is a public-key encryption algorithm used in secure communication protocols. RSA uses a BST to generate public and private keys.
BSTs can be used to compress data by storing frequently occurring values in a smaller space and less frequently occurring values in a larger space. This technique is used in many applications, including image and audio compression, data transmission, and file compression.
What are some advantages of using a Binary Search Tree?
BST is fast in insertion and deletion when balanced. It is fast with a time complexity of O(log n).
BST is also for fast searching, with a time complexity of O(log n) for most operations.
BST is efficient. It is efficient because they only store the elements and do not require additional memory for pointers or other data structures.
We can also do range queries – find keys between N and M (N <= M).
BST code is simple as compared to other data structures.
BST can automatically sort elements as they are inserted, so the elements are always stored in a sorted order.
BST can be easily modified to store additional data or to support other operations. This makes it flexible.
What are some disadvantages of using a Binary Search Tree?
The main disadvantage is that we should always implement a balanced binary search tree. Otherwise the cost of operations may not be logarithmic and degenerate into a linear search on an array.
They are not well-suited for data structures that need to be accessed randomly, since the time complexity for search, insert, and delete operations is O(log n), which is good for large data sets, but not as fast as some other data structures such as arrays or hash tables.
A BST can be imbalanced or degenerated which can increase the complexity.
Do not support some operations that are possible with ordered data structures.
They are not guaranteed to be balanced, which means that in the worst case, the height of the tree could be O(n) and the time complexity for operations could degrade to O(n).
