Graphs & Trees

Question 1

What are the different type of traversals for a binary search tree?

Answer 1

1. Preorder NLR (node, left subtree then right subtree)
2. Inorder LNR
3. Postorder LRN
4. Level order (BFS- breadth first search)

Question 2

What kind of traversal is preferred for sorting ?

Answer 2

Inorder will give ascending elements in BST

Question 3

What kind of traversal is preferred for deletion of nodes ?

Answer 3

Postorder

Question 4

Mathematical expressions can be handled/calculated using which traversal?

Answer 4

Postorder. by using postorder to push the values in a stack and pop two values when an operator is encountered

Question 5

Traversal Iteratively for preorder (what data structure to use?)

Answer 5

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;
} }

Question 6

Level order traversal or BFS in a Tree (what data structure to use?)

Answer 6

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

Question 7

How do you do level order traversal

Answer 7

/**
 * 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;
    }

Question 8

What is the difference between Binary Tree and Binary search tree (BST)?

Answer 8

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

Question 9

What is a Balanced Binary Tree?

Answer 9

The left and right subtree must differ in height by no more than 1

Question 10

What is a Complete Binary Tree?

Answer 10

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

Question 11

Define Leaf

Answer 11

Node with no child

Question 12

What is a Full Binary Tree?

Answer 12

No node will have only 1 child, i.e., it can have either 2 or 0 child

Question 13

What is a Perfect Binary Tree?

Answer 13

All the nodes have 2 children except for the last level

Question 14

What is the Depth of a Balanced Binary Search Tree with total N elements ?

Answer 14

log N

Question 15

What is the Criteria for Min Heap Tree?

Answer 15

• It has to be Complete Binary Tree

- The root node is minimum

Question 16

How do you perform Insertion for Min Heap Tree?

Answer 16

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.

Question 17

What is the Runtime Complexity for Insertion into Min Heap Tree?

Answer 17

O(log N)

Question 18

How do you remove the min element from Min Heap Tree?

Answer 18

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)

Question 19

What is a Graph?

Answer 19

1. A tree is a graph but not all graphs are trees
2. A graph can be directed or undirected
3. A graph therefore can have cycles
4. A graph is a collection of nodes with edges between(some of ) them

Question 20

What are the ways to represent graphs?

Answer 20

1. Adjacency lists

2. Adjacency matrix

Question 21

What is Adjacency list?

Answer 21

Adjacency list : every nodes stores a list of adjacent nodes.
class graph{
Node[] nodes;
}
class Node{
int val;
Node[] neighbours;
}

Question 22

What is adjacency matrix?

Answer 22

A matrix n*n for n nodes

where matrix[i][j] contains true(1) if there is an edge between i and j else 0(false)

Question 23

What methods are present for Graph Searching?

Answer 23

DFS and BFS
DFS: start at root and explore each branch completely before moving on to the next branch
BFS: start at root and explore all neighbours and then move on the next level

Question 24

Where can DFS be used?

Answer 24

if we want to visit all nodes
---------------------------------
DFS (to visit a vertex x)
---------------------------------
- Mark x as visited
- Recursively visit all unmarked vertices w adjacent to x
---------------------------------

Question 25

Where can BFS be used?

Answer 25

if we want to find the shortest path/just any path between 2 nodes. Queues are well suited for BFS. So you want the GPS to use BFS :)

Question 26

What is the most common approach for a Tree construction(including tries)?

Answer 26

recursion

Question 27

Trie Node Representation

Answer 27

``` // each Node in Trie public class Node{ public Object val; public Node[] next = new Node[R]; // R could be a set of ASCII char, for instance, 128 or 256 chars } ```

Question 28

Trie Representation

Answer 28

public class Trie{ private int R = 256; // extended ASCII private Node root; // ref: Node representation public void put(String key, TValue value){ root = put (root, key, value, 0); } ``` public root put(Node node, String key, TValue val, int d) { if (node == null) { node = new Node(); } if (d == key.Length) { node.Value = val; return node; } ``` ``` char c = key.ChartAt(d); node.next[c] = put (node.next[c], key, val, d+1); // recursive call return node; } } ```

Question 29

What data structure can be used to perform spell checking?

Answer 29

``` Trie can be used. the keys(words) can be represented by nodes and the leaves will have a value of 1 indicating they are a valid spelling ```

Question 30

Mazes can be depicted as?

Answer 30

Graphs with intersection as nodes and passage between them as edges. DFS can be used to explore a maze.

Question 31

Design Pattern for Graph Processing

Answer 31

A simple API design pattern for a graph could be: ``` public class Paths{ Paths(Graph G, int s) // find paths in G from source s bool hasPathTo(int v) // is there a path from s to v? Iterable pathTo(int v) // path from s to v } ```

Question 32

How would you create a BST with minimal height given an sorted array of integers?

Answer 32

A minimal BST is one which has almost equal number of nodes on its left and right

Question 33

Runtime for BFS/DFS

Answer 33

O(N+E) where N is number of nodes and E is edges

Question 34

For PreOrder, InOrder and PostOrder traversal why is it recommended to traverse iteratively than recursively

Answer 34

Because if the depth of the tree is very large we can run into stack overflow problem with recursive approach

Question 35

Usually a tree problem can be solved recursively using either __ or __

Answer 35

top-down or bottom-up approach.

Question 36

What's the top down approach for solving a tree or recursive problem

Answer 36

We make use of a parameter (params in eg below) to be passed in each recursive call. "Top-down" means that in each recursive call, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively. So the "top-down" solution can be considered as a kind of preorder traversal. To be specific, the recursive function, top_down(root, params) works like this: 1. return specific value for null node 2. update the answer if needed // answer -- params 3. left_ans = top_down(root.left, left_params) // left_params -- root.val, params 4. right_ans = top_down(root.right, right_params) // right_params -- root.val, params 5. return the answer if needed // answer -- left_ans, right_ans

Question 37

Between adjacent list or matrix which one is preferred way to represent trees

Answer 37

list since it takes less space, for a matrix we will use only 2(N-1) cells of the available N^2 space

Question 38

What is the bottom up approach for solving a tree or recursive problems

Answer 38

"Bottom-up" is another recursive solution. In each recursive call, we will firstly call the function recursively for all the children nodes and then come up with the answer according to the returned values and the value of the current node itself. This process can be regarded as a kind of postorder traversal. A "bottom-up" recursive function bottom_up(root) will be something like this: 1. return specific value for null node 2. left_ans = bottom_up(root.left) // call function recursively for left child 3. right_ans = bottom_up(root.right) // call function recursively for right child 4. return answers // answer

Question 39

When you are talking about depth of a tree, what exactly are you referring to?

Answer 39

It's the number of edges till the leaf nodes. IT IS NOT THE LEVELS

Question 40

Does topological sort work on cyclic graphs?

Answer 40

No. Topological sort works only on Directed Acyclic graphs (DAG). A cyclic graph would break the precedence constraint. One can conclude, that the rooted trees are always DAG without any cycles A follow up problem as such is to identify if there are any cycles in the graph, which will identify whether the topological sort is possible or not

Question 41

When is topological sort used

Answer 41

When we are given a set of tasks to be completed with precedence constraints or precedence scheduling. For instance, the prerequisites for a course work. Topological sort works with Directed graphs (DiGraphs). After the topological sort, we will end up with drawing a graph with all the arrows pointed upwards.

Question 42

Which search can be used to solve the topological sort problem

Answer 42

1. Run DFS | 2. Return vertices in reverse postorder - we use a Stack of vertices to store the reverse postorder which is our answer

Question 43

Are topological ordering unique

Answer 43

No. One can get different answers based on the node selected. The basic idea is that all the dependencies need to be built before.

Question 44

What kind of search would you use to implement web crawler

Answer 44

BFS

Question 45

How do we verify if a graph is a tree or not

Answer 45

For a graph to be tree 1. There should be no cycles 2. For N nodes there should be N-1 edges