DSA Day-25
Hey Everyone!!!
I hope you are doing well! In the previous segment of this series, I covered some important questions and provided links for practice on ‘Trees’.
Now, we’ll be moving on to the self-evaluation portion so that you can analyse your preparation level and move on accordingly.
1: Which of the following statements is false ?
A.Every tree is a bipartite graph
B.A tree contains a cycle
C.A tree with n nodes contains n-1 edges
D.A tree is a connected graph
2. A complete binary tree with the property that the value at each node is at least as large as the values at its children is called
A.binary search tree
B.Binary Tree
C.Completely balanced tree
D.Heap
3. Which of the following statements are correct ?
I. If each tree node contains a father field, then it’s not necessary to use either stack or threads
II. Traversal using father pointers is more time efficient than traversal of a threaded tree
III. A in-threaded binary tree is defined as binary tree that is both left-in threaded and right-in
threaded.
A.II and III
B.I and III
C.I and II
D.None of these
4. A binary tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20,58, 91, 3,8,37, 60, 24
The number of nodes in the left and right of the root respectively is
A.(7,4)
B.(4,7)
C.(6,3)
D.(3,6)
5. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves
A. cannot have more than 19 nodes
B.cannot have more than 17 nodes
C. has exactly 17 nodes
D. has exactly 19 nodes
6. Consider the following code segment in C to traverse a binary tree using the preorder
typedef struct tree {
int info;
struct *left; struct *right;
}
node;
void preorder(node *tree) {
if (t) {
Statementl
Statement2
Statement3
}
}
The above Statements should be
A. preorder(tree->right); preorder(tree->left); printf(“%d”, tree->info);
B. preorder(tree->left); preorder(tree->right); printf(“%d”, tree->info);
C. preorder(tree->left); printf(“%d”, tree->info); preorder(tree->right);
D. printf(“%d”, tree->info); preorder(tree->left); preorder(tree->right);
7. If a node in a BST has two children, then its inorder predecessor has
A. no left child
B. two children
C. no right children
D. no child
8. https://www.interviewbit.com/problems/invert-the-binary-tree/
9. https://www.interviewbit.com/problems/bst-iterator/
10. https://www.interviewbit.com/problems/vertical-order-traversal-of-binary-tree/
Above coding questions have been asked by top companies like Microsoft, Google, Apple, Facebook, Amazon etc.. So, make sure that you solve these questions along with the ones that I provided in the previous segment as these are few questions that are repeatedly asked in interviews.
Solutions:
- B
- D
- B
- A
- D
- D
- C
Advanced Level Questions + Hints on Trees : Personal Notes
1. Find distance between two given nodes in a binary tree/ binary search tree.
- Find LCA
public static Node LCA(Node root, int n1, int n2)
{
if (root == null)
return root;
if (root.value == n1 || root.value == n2)
return root;
Node left = LCA(root.left, n1, n2);
Node right = LCA(root.right, n1, n2);
if (left != null && right != null)
return root;
if (left != null)
return LCA(root.left, n1, n2);
else
return LCA(root.right, n1, n2);
}
// Returns level of key k if it is present in
// tree, otherwise returns -1
- Find the distance of each node from LCA
public static int findLevel(Node root, int a, int level)
{
if (root == null)
return -1;
if (root.value == a)
return level;
int left = findLevel(root.left, a, level + 1);
if (left == -1)
return findLevel(root.right, a, level + 1);
return left;
}
- Add the distance
public static int findDistance(Node root, int a, int b)
{
Node lca = LCA(root, a, b);
int d1 = findLevel(lca, a, 0);
int d2 = findLevel(lca, b, 0);
return d1 + d2;
}
Time Complexity: O(N)
2. Given a BST (Binary Search Tree) , Each node value should replace with sum of the node which are greater-than the given node.
conditions :
No Extra space / variable can use
Modify the existing tree in optimal way.
- Replace root.val = root.right.val
5. Given two (binary) trees, return the first pair of non-matching leaves
Tree 1: A, B, C, D, E, null, null
Tree 2: A, D, B
Output: (E,B)
- Do an inorder traversal and create one list for each tree to store leaves
- Return the first unequal leaves from the list
Time Complexity: O(M+N)
3. Suggest a data structure and implement efficient phrase search along with word search in a huge chunk of text.
- Trie can be used
- Time Complexity for searching : O(N)
4. Given the root of a binary tree containing integers, print the columns of the tree in order with the nodes in each column printed top-to-bottom.
static void getVerticalOrder(Node root, int hd,
TreeMap<Integer,Vector<Integer>> m)
{
// Base case
if(root == null)
return;
//get the vector list at 'hd'
Vector<Integer> get = m.get(hd);
// Store current node in map 'm'
if(get == null)
{
get = new Vector<>();
get.add(root.key);
}
else
get.add(root.key);
m.put(hd, get);
// Store nodes in left subtree
getVerticalOrder(root.left, hd-1, m);
// Store nodes in right subtree
getVerticalOrder(root.right, hd+1, m);
}
Time Complexity: O(N)
5. Assuming you have a binary tree which stores integers, count the number of nodes whose value is lower than the value of its upper nodes.
- Create a list
- if root.val < pval (parent value) { list.add(root.val); }
Time Complexity: O(N)
6. Given the Pre-order of the BST .check if each non-leaf node has only one child.Linear Time is expected.
boolean checkOneChild(int[] preorder)
{
for(int i=0; i<preorder.length-2; i++)
{
int a = preorder[i]-preorder[i+1];
int b = preorder[i]-preorder[preorder.length-1];
if(a*b<0)
return false;
if(a*b==0)
{
if(a+b<0)
return false;
}
}
}
The above code is checking if the child node and the leaf node(last node) lies on the same side (Left or Right) of the Sub Tree. Means if the a*b is <0 means
1. Child is smaller then parent(i) and Last Node is greater then parent(i)
2. Child is Greater then parent(i) and Last Node is smaller then parent(i)Hope this was helpful!!! Good luck and keep practicing.
