Recitations Flashcards
(16 cards)
What is inorder traversal
What is post order traversal
what is pre order traversal
do all the opertations on the tree
0
1 2 3 4 7 8 5 6
Inorder -
left root right
post order
left right root
pre order - normal
root left right
536140728
563417820
013564278
preorder: 45,32,11,29,64,50
construct a BST
45
32 64
11 50
29
Given the following traversals, construct the general binary tree and list the post-order traversal.
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
post order DEBFCA
tree:
A B c d e f
A complete binary tree is a binary tree in which every level of the tree has the maximum number of nodes possible except possibly the deepest level. Also, at the deepest level, the nodes are as far left as possible. What are the formulas for the maximum and minimum number of nodes and internal nodes in a complete binary tree of height h.
Formulas can be derived from the max # of nodes in a complete binary tree of height h.
The formula for min # of nodes in a complete binary tree of height h: 2^h
The formula for max # of nodes in a complete binary tree of height h: 2^(h+1) - 1
The formula for min # of internal nodes in a complete binary tree of height h: 2^(h-1)
The formula for max # of internal nodes in a complete binary tree of height h: 2^h - 1
What is the minimum and maximum number of nodes in a complete binary tree with a height of 4? What is the number of internal nodes?
Nodes: Min: 16 Max: 31
Internal: min: 8 max: 15
A full binary tree is a binary tree in which every non-leaf node has 2 children, and all leaves have the same depth. What is the minimum and maximum number of nodes in a binary tree with a height of 4? What is the number of internal nodes? What is a full binary tree’s relation to a complete binary tree?
31 nodes and 15 internal nodes
Write functions that allow us to validate whether the tree is a valid bst
public boolean isValidBst(TreeNode root)
if ( root == null){
return true ;
}
return depthFirst(root,null,null);
}
private boolean depthFirst( TreeNode root, Integer min, Integer max){
if ( root ==null){
return true;
}
if ( min != null && root.val <= min ) ||(max != null && root.val >= max){
return false;
}
return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
}
Given a sorted array, write function(s) to convert that array into a BST (return the root node).
public TreeNode arrayToBST(int [] nums){
return builder( nums, 0 , nums.length-1)
}
public TreeNode builder(int [] nums, start, end){
if ( start > end){
return null;
}
int mid = (start + end) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = builder( nums, start, mid-1)
root.right= builder(nums, mid+1,end)
return root;
T/F Given a graph with n vertices and m edges, the space complexity of an adjacency matrix
is 𝑂(𝑛𝑚).
B) For an undirected graph, the adjacency matrix is asymmetrical.
C) It is faster to add or remove an edge on an adjacency matrix compared to an edge list.
When representing a graph, an adjacency matrix is always more memory efficient
than edge lists.
E) Dijkstra’s shortest-path algorithm finds the path with the least number of edges
from a source to every other vertex of a graph.
F
F
T
F
F
Design an algorithm that returns true if there exists a path between two vertices in the
graph.
boolean isReachable(Vertex src, Vertex dst)
{
// use breadth-first traversal to find a path from src to dst.
Queue<Vertex> bftQueue = new Queue<Vertex>();
src.visited = true;
bftQueue.enqueue(src);
Vertex curr;
while(!bftQueue.isEmpty())
{
curr = bftQueue.dequeue();
for(Vertex v : curr.getNeighbors())
{
if(v.equals(dst)) return true;
if(!v.visited)
{
v.visited = true;
bftQueue.enqueue(v);
}
}
}
return false;
}</Vertex></Vertex>
True or false
1. In a 2-3-4 Tree, insertion can be performed on any node so long as the other nodes
are adjusted accordingly
2.Deleting the highest priority element and reorganizing the heap will only take O(log n)
time.
3.A red-black tree may have all red nodes.
4.The following array is a max-heap:
Int maxHeap[] = {10,5,3,4,1};
F
T
F
T
What is the max height of a Red-Black Tree with 6 nodes? Draw an example of
this Red-Black Tree.
Given an integer array nums, return true if any value appears at least twice in the
array, and return false if every element is distinct. (Use HashMap)
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
public boolean containsDuplicate(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num: nums) {
if (map.get(num) == null) {
map.put(num, 1);
} else return true;
}
return false;
}
Given two arrays A[] and B[] of size n. It is given that both array individually
contains distinct elements. We need to find the sum of all elements that are not common.
Input : A = {1, 5, 3, 8}, B = {5, 4, 6, 7}
Output : 29
Explanation: 1 + 3 + 4 + 6 + 7 + 8 = 29
public static int findSum(int[] A, int[] B, int n)
{
// Insert elements of both arrays
HashMap<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < n; i++)
{
if (hash.containsKey(A[i]))
hash.put(A[i], 1 + hash.get(A[i]));
else
hash.put(A[i], 1);
if (hash.containsKey(B[i]))
hash.put(B[i], 1 + hash.get(B[i]));
else
hash.put(B[i], 1);
}
// calculate non-overlapped sum
int sum = 0;
for (Map.Entry entry : hash.entrySet())
{
if (Integer.parseInt((entry.getValue()).toString()) == 1)
sum += Integer.parseInt((entry.getKey()).toString());
}
return sum;
}
Find the difference between the strings.
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random
position.
Return the letter that was added to t.
Input: s = “abcd”, t = “abcde”
Output: “e”
Input: s = “”, t = “y”
Output: “y”
public char findTheDifference(String s, String t) {
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0; i < s.length(); i++){
if(map.containsKey(s.charAt(i))){
map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
}else{
map.put(s.charAt(i), 1);
}
}
for(int i = 0; i < t.length(); i++){
if(!map.containsKey(t.charAt(i)) || map.get(t.charAt(i)) == 0){
return (char) t.charAt(i);
}
map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
}
return ‘!’; // never returned assuming s and t are correct.
}
