Graphs & Trees Flashcards
What are the different type of traversals for a binary search tree?
- Preorder NLR (node, left subtree then right subtree)
- Inorder LNR
- Postorder LRN
- Level order (BFS- breadth first search)
What kind of traversal is preferred for sorting ?
Inorder will give ascending elements in BST
What kind of traversal is preferred for deletion of nodes ?
Postorder
Mathematical expressions can be handled/calculated using which traversal?
Postorder. by using postorder to push the values in a stack and pop two values when an operator is encountered
Traversal Iteratively for preorder (what data structure to use?)
It can be done using a LinkedList to act as a stack
class Solution {
public List preorderTraversal(TreeNode root) {
LinkedList result = new LinkedList<>();
LinkedList stack = new LinkedList<>();
if(root == null)
return result;
stack.add(root);
while(!stack.isEmpty()) {
TreeNode item = stack.pollLast();
result.add(item.val);
if(item.right != null)
stack.add(item.right);
if(item.left != null)
stack.add(item.left);
}
return result;
} }
Level order traversal or BFS in a Tree (what data structure to use?)
The algorithm starts with a root node and visit the node itself first. Then traverse its neighbors, traverse its second level neighbors, traverse its third level neighbors, so on and so forth.
Typically, we use a queue to help us to do BFS
How do you do level order traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public IList> TraverseLevelOrderOrBFS(TreeNode root)
{
IList> levelOrderedNums = new List>();
var queueToHoldNumsAtCurrentLevel = new Queue();
if (root == null)
{
return levelOrderedNums;
}
queueToHoldNumsAtCurrentLevel.Enqueue(root);
while(queueToHoldNumsAtCurrentLevel.Count > 0)
{
IList numsAtCurrentLevel = new List();
for(int i = 0; i < queueToHoldNumsAtCurrentLevel.Count; i++)
{
// dequeue all the nodes at current level
var node = queueToHoldNumsAtCurrentLevel.Dequeue();
numsAtCurrentLevel.Add(node.Value);
if (node.LeftNode != null)
{
queueToHoldNumsAtCurrentLevel.Enqueue(node.LeftNode);
}
if (node.RightNode != null)
{
queueToHoldNumsAtCurrentLevel.Enqueue(node.RightNode);
}
}
levelOrderedNums.Add(numsAtCurrentLevel);
}
return levelOrderedNums;
}
What is the difference between Binary Tree and Binary search tree (BST)?
Binary tree and Binary Search Tree both have 2 children for every node.
But for BST all the values in the left subtree must be less than the right subtree
What is a Balanced Binary Tree?
The left and right subtree must differ in height by no more than 1
What is a Complete Binary Tree?
Every level of the tree is fully filled except for perhaps the last level to the extent that the last level is filled, it’s filled left to right
Define Leaf
Node with no child
What is a Full Binary Tree?
No node will have only 1 child, i.e., it can have either 2 or 0 child
What is a Perfect Binary Tree?
All the nodes have 2 children except for the last level
What is the Depth of a Balanced Binary Search Tree with total N elements ?
log N
What is the Criteria for Min Heap Tree?
- It has to be Complete Binary Tree
- The root node is minimum
How do you perform Insertion for Min Heap Tree?
You start from left to right in the bottom most level to find if there is an empty spot. If it is add the element there, else try to find an empty spot in the level above.
Once inserted keep swapping the element with the parent until parent value is less than child, essentially bubbling up the new value.
What is the Runtime Complexity for Insertion into Min Heap Tree?
O(log N)
How do you remove the min element from Min Heap Tree?
Reading the min element is a straightforward operation of just reading the top element.
But if you have to remove it entirely from the heap, you basically swap the min element with the largest element in the last level and then let the largest element bubble down. Complexity O(log N)
