## Trees and Graphs Interview Questions

- 0of 0 votes
Given a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)

Node restore(List<Integer> list)

Example Tree:

5

/ \

3 2

/ / \

1 6 1

- 0of 0 votes
You are given a NxN boolean matrix, where matrix(i,j) will be one if 'i' is a parent of 'j' in a tree, otherwise, it is zero.

Construct this tree.

- 0of 0 votes
You are given an array of nodes where each node consists of node name, isValid flag, and parent Node index. so, this array actually represents a tree(forest). where root node has -1 as its index for the parent node. rest all node have their parent's index value.

You will be given this array and an index. You have to cut down the subtree from the index. Cutting down a tree means, making all the nodes of that subtree false(Isvalid flag).

He was expecting O(N) solution.

- 0of 0 votes
Q 4. You are given a binary tree, and you have to return list of lists of node. where same level nodes should be in the same list, nodes are in opositive order in next list from the previous list

Ex:`4 / \ 3 5 / \ \ 1 10 -4`

Output would be

[[4], [5, 3], [1, 10, -4]]

Desigred Complexity : O(N) + O(N).

- 0of 0 votes
You are given a BST of integers and an integer K. You have to find the smallest greater integer then K in the BST.

Ex`40 --- 50 --- 80 | | | 45 20 --- 30 | | 10 K = 35 Output: 40`

- 1of 1 vote
Given the following set of strings, write a function that stores this information.

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/SSDs

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/SSDs

// /Electronics/TVs

// /Electronics/Computers/Graphics Cards

// /Electronics/TVs

// /Electronics/TVs

// /Garden

// /Automotive/Parts

Your datastructure should be able to provide information as such:

// / = 11

// /Electronics = 9

// /Electronics/Computers = 6

// /Electronics/Computers/Graphics Cards = 4

// /Electronics/TVs = 3

// etc

// ["/Electronics/Computers/Graphics Cards", "/Garden"]

- 0of 0 votes
Q1. You are given a binary search tree (with unique values) and two values. You need to find their lowest common ancestor. (Expected Complexity O(log(n)) + O(1))

Q2. Now let's assume the tree has duplicates, and when a duplicate number come, the insertion logic chooses left node. (Expected Complexity O(log(n)) + O(1))

Q3.Now let's assume the input tree is a binary tree instead of the binary search tree.(Expected Complexity O(n) + O(1))

- 0of 0 votes
/**

* A tournament tree is a binary tree

* where the parent is the minimum of the two children.

* Given a tournament tree find the second minimum value in the tree.

* A node in the tree will always have 2 or 0 children.

* Also all leaves will have distinct and unique values.

* 2

* / \

* 2 3

* / \ | \

* 4 2 5 3

*

* In this given tree the answer is 3.

*/`class Node { Integer value; Node left, right; Node(Integer value, Node left, Node right) { this.value = value; this.left = left; this.right = right; } } class Solution { /** * This should return the second minimum * int value in the given tournament tree */ public static Integer secondMin(Node root) { } }`

- 0of 0 votes
find the given Binary tree is mirrored tree or not

should be like

60

/ \

30 30

/ \ / \

20 50 50 20

- 0of 0 votes
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.

- 2of 2 votes
Given a Binary tree and value X. Find X in the tree and return its parent

X:

10

4 3

5 7 9 8

If X = 7, return 4

- -4of 4 votes
na

- -3of 3 votes
Convert an unordered tree to a binary tree

- 1of 1 vote
merge two binary search trees

- 0of 0 votes
You are given a binary tree. Each node in the tree is a house and the value of node is the cash present in the house. A thief can rob houses in alternate levels only. If thief decides to rob house at level 0 then he can rob houses in levels 2,4,6... or he can rob houses in levels 1,3,5,7...Find out the maximum possible amount thief can rob.

- 1of 3 votes
Create a function to calculate the height of an n-ary tree.

- 0of 0 votes
From here : question?id=5660692209205248

In-order traversal:

A->B->C->D->E->F->H->L->M-P->R->S->T

Write a function (pseudo-code is fine) that given a starting node, advances to the next in-order node in a binary tree.

Please also provide a data-structure definition of a node.

- 0of 0 votes
Given an n-ary tree, find the longest sequence in it. The sequence doesn't end to start at the root. It can go from leaf to leaf.

- 0of 0 votes
Need to traverse below n-ary in postorder and throw error message if the node are cyclic

Node001

/ | \

/ | \

/ \ \

Node002 Node003 Node004

/ / | \

/ / | \

Node005 Node006 Node007 Node008

/

/

Node009

\

\

Node003

In above case it should through error because Node009 has child Node003 which is derived from it.

- 0of 0 votes
Hi Implemented this sample code for N-ary postOrder Traversal.

Now i want to throw error statement id the parent node is dependent on child.

Can some one help

package dependencyAlgorithm;

import java.util.*;

public class Dependency

{

class MainRule

{

String ruleName;

ArrayList<MainRule> subrule;

public MainRule(String name)

{

this.ruleName=name;

subrule=new ArrayList<>();

}

}

public static void postOrder(MainRule rootRule)

{

Stack<List<MainRule>> stack = new Stack<>();

MainRule rule = rootRule;

List<MainRule> list = null;

while (true)

{

if(rule != null)

{

list = rule.subrule;

for(int i=0;i<list.size();i++)

{

if(rule.ruleName == list.get(i).ruleName)

break;

}

rule = null;

if(list!=null && list.size()>0)

{

//push the list in the stack (do not modify original tree structure).

stack.push(new ArrayList<>(list));

//get first item from this list

rule = stack.peek().get(0);

System.out.print("\n1 ListSize: "+list.size());

}

}

else if (!stack.isEmpty())

{

System.out.print("\n2 \n");

list = stack.pop();

System.out.print("\n2 ListSize: "+list.size());

rule = list.remove(0); //shift left

System.out.print("\n2.1 ListSize: "+list.size());

System.out.print("\n"+rule.ruleName+" ");

rule = null;

if(list.size()>0)

{

System.out.print("\n3 ListSize "+list.size());

stack.push(list); //push back remaining list into stack

rule = stack.peek().get(0); //prepare for next iteration

}

}

else

break;

}

System.out.println(rootRule.ruleName);

}

/*

Fml001

/ | \

/ | \

/ | \

Fml002 C001_Base Tot001

/ / | \

/ / | \

Fml003 Fml004 R001_Base R001_TxPat

/

/

Tot002

\

\

C001_TxPat

*/

public void createBinaryTree()

{

MainRule rootRule;

MainRule Fml001 =new MainRule("Fml001");

MainRule Fml002=new MainRule("Fml002");

MainRule Fml003=new MainRule("Fml003");

MainRule Fml004=new MainRule("Fml004");

MainRule C001_Base=new MainRule("C001_Base");

MainRule R001_Base=new MainRule("R001_Base");

MainRule Tot001=new MainRule("Tot001");

MainRule Tot002 =new MainRule("Tot002");

MainRule R001_TxPat =new MainRule("R001_TxPat");

MainRule C001_TxPat =new MainRule("C001_TxPat");

rootRule=Fml001;

rootRule.subrule.add(Fml002);

rootRule.subrule.add(C001_Base);

rootRule.subrule.add(Tot001);

Fml002.subrule.add(Fml003);

C001_Base.subrule.add(Fml004);

C001_Base.subrule.add(R001_Base);

C001_Base.subrule.add(R001_TxPat);

R001_Base.subrule.add(Tot002);

Tot002.subrule.add(C001_TxPat);

postOrder(rootRule);

}

public static void main(String[] args)

{

Dependency dependency=new Dependency();

// Creating a tree structure

System.out.println("Path Traversed:");

dependency.createBinaryTree();

}

}

- 1of 1 vote
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)

- 3of 3 votes
Given a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.

Example:`Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5`

Edit: Thanks, wangchenClark0512, forgot about C to D

Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.

Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles

- 0of 0 votes
Suggest a data structure and implement efficient phrase search along with word search in a huge chunk of text.

- 6of 6 votes
You are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.

Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)

Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.

Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)

The total run-time after returning everything should be O(n).

Examples:`Input: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45`

- 1of 1 vote
There are n number of conference rooms available in a company for the meeting. You need to book a meeting for a particular time slot. Write an algorithm to determine the number of conference rooms available for the meeting with given start time and end time.

Hint: any conference room with non- overlapping meeting will be selected.

- 0of 0 votes
Write a program to identify if a given binary tree is balanced or not.

- 4of 4 votes
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.

`Input: 6 / \ 3 4 / \ \ 5 1 0 / \ / 9 2 8 \ 7 Output: 9 5 3 2 6 1 7 4 8 0 Input: 1 / \ 2 3 / \ / \ 4 5 6 7 When two nodes share the same position (e.g. 5 and 6), they may be printed in either order: Output: 4 2 1 5 6 3 7 or: 4 2 1 6 5 3 7`

- 0of 0 votes
Given a sorted integer array. Convert it to a balanced BST (Size of array is given)

- 3of 3 votes
Given a forest of balanced binary trees and two nodes, n1 and n2, find the closest common parent of n1 and n2. Nodes have parameters "parent", "left" and "right", and you cannot access the values of the nodes. If n1 and n2 are not on the same tree, return NULL.

Try to do this in O(log(n)) time and O(1) space.

- 1of 1 vote
You have a BST and you need to assign an appropriate value to neighbor of all nodes (Explained in below example)

Node Structure`node { node leftChild, node rightChild, T data, node neighbor }`

A

/ \

B C

/ \ \

D E F

Based on above tree,

Node: Neighbor

A: NULL

B: C

D: E

E: F