## Trees and Graphs Interview Questions

- 0of 0 votes
First common Ancestor of Binary tree . Java Solution needed.

Class Node {

Node Parent;

Node LeftChild;

Node rightChild;

int val;

}

publlic Node firstAncestor(Node leftNode, Node rightNode){

// We don't get the root node here. From left and right child we need to find it's parent and find the lowest common ancestor.

}

- 0of 0 votes
Given a binary tree, where each node represents an integer, find the max value of path sum.

- 0of 0 votes
Suppose you have a list of tasks which need to be executed. Some of these tasks have dependencies which must be executed before they are. Please provide a method which, when given a list of tasks, will provide a valid ordering in return.

Example:

Input: [ A, B, C, D ]

A <- B, C

B <- C, D

D <- C

Return: [ C, D, B, A ]

- -1of 1 vote
Define a class 'Space' which has a member string variable that indicates if the space is a "tree", a "house" or an empty space and another member variable that will store the 'space neighbors' (left, right, up and down only)

Given a 'Grid' (list) of Spaces write the code for the findAll(start) method to find all the trees and houses given a 'Space' as start point

Example, Grid of 'Spaces':

T 0 0 H 0

0 0 0 0 0

H H T H 0

Where Ts are trees and Hs are houses

- 0of 0 votes
Given a Tree where each node contains an attribute say color(R,G,B... etc). find subtree with maximum number of attributes.

Input:

G

/ \

B R

/ \ / \

B B R R

/ \ / \

B R R R

Output:

Input:

R

/ \

R R

\ / \

R R R

- 0of 0 votes
let's say you're given an arbitrary list of relations r1 and r2 from objects in a set of arbitrary size. find the size of th largest subset with the property that no two are related. for e.g., given set S = {a,b,c,d,e,f} and relations {a,d}, {b,c}, {a,c}, {a,e}, find the subset of S such that no two a connected.

- 0of 0 votes
Given a root to a binary tree, find the level of the tree with the minimum sum.

for example:

50

/ \

6 2

/ \ /

30 80 7

the answer is: level 2

- 2of 2 votes
A binary tree is started burning from a leaf node. What is the time(1ms to burn from node to node) it takes to entire tree get burned? The fire will spread to all the paths from a node.

- 0of 0 votes
Given a binary tree, write a recursive method boolean method(int x, int y) which will return true

1. if node y (meaning a node with a value of int y) is a node that is contained in one of the two possible subtrees of x,

2. true if x==y, and a node with a value x==y exists, otherwise

3. return false,

basicallly whether x contains y? I had a question like this on my exam, I solved this problem using four arguments in my function. I wonder whether it is even possible to solve it with only 2 int arguments and recursively.

- 0of 0 votes
Given a list/array of "Assign" trees with integers, operators and variables, return the result of the requested "Result" tree expression.

Example:`"Assign" / \ "x" "+" / \ 2 3 "Assign" / \ "y" "-" / \ 5000 30 "Assign" / \ "z" "*" / \ 50 x "Return" \ "-" / \ z "*" / \ 1 y`

- 0of 0 votes
I've got these trees of integers; they're like regular trees, but they can share nodes.

I need to know if any branch of this tree sums to 100.

7

/ \

8 6

/ \ / \

2 3 9

/ \ / \ / \

5 4 1 100

Follow up question was how would you change the code to handle negative numbers.

- 0of 0 votes
Find distance between any two nodes of binary tree and binary search tree.

- 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`

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