## Amazon Interview Question for SDE-2s

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 5 vote

breadth traversal approach; also can be implemented with Deep traversal like pre-order

``````public int? FindParent(TreeNode root, int value)
{
if (root == null || root.Value == value)
return null;

var queue = new Queue<TreeNode>();
queue.Enqueue(root);

while (queue.Count > 0)
{
var p = queue.Dequeue();

if (p.Left != null)
{
if (p.Left.Value == value)
return p.Value;
queue.Enqueue(p.Left);
}

if (p.Right != null)
{
if (p.Right.Value == value)
return p.Value;
queue.Enqueue(p.Right);
}
}

return null;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````def find_parent(root, val):
if not root:
return None

if root.left and root.left.data == val:
return root

if root.right and root.right.data == val:
return root

find_left = find_parent(root.left, val)
if find_left:
return find_left

find_right = find_parent(root.right, val)
if find_right:
return find_right

return None``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def return_parent(tree, x, par):
if tree:
if tree.val == x:
return par
return return_parent(tree.left, x, tree) or return_parent(tree.right, x, tree)

return None``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

So the Binary tree is not a sorted binary tree. In this case we have to perform a full scan:

``````public class Node
{
public Node Left { get; set; }
public Node Right { get; set; }
public int Value { get; set; }

public override string ToString()
{
return Value.ToString(CultureInfo.InvariantCulture);
}
}

public class TreeSearcher
{
public static Node Search(Node parent, int valueToSearch)
{
return SearchInternal(parent, valueToSearch, null);
}

private static Node SearchInternal(Node n, int valueToSearch, Node parentNode)
{
if (n == null)
return null;

if (n.Value == valueToSearch)
return parentNode;

var val = SearchInternal(n.Left, valueToSearch, n);
return val ?? SearchInternal(n.Right, valueToSearch, n);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Original case:

``````static <T extends Comparable<T>> TreeNode<T> findParentForNodeInBT(TreeNode<T> root, T value) {

if (root == null) {
return null;
}

TreeNode<T> currentNode = root;
if (currentNode.val.compareTo(value) == 0) {
return null;
}

while (!queue.isEmpty()) {

currentNode = queue.pollFirst();
// follow the right branch (if possible)
if (currentNode.right != null) {
if (currentNode.right.val.compareTo(value) == 0) {
return currentNode;
}
}
// follow the left branch (if possible)
if (currentNode.left != null) {
if (currentNode.left.val.compareTo(value) == 0) {
return currentNode;
}
}
}

return null;
}``````

If the binary tree is a binary search tree:

``````static <T extends Comparable<T>> TreeNode<T> findParentForNodeInBST(TreeNode<T> root, T value) {

if (root == null) {
return null;
}

TreeNode<T> currentNode = root;
if (currentNode.val.compareTo(value) == 0) {
return null;
}

while (true) {
// follow the right branch (if possible)
if (currentNode.val.compareTo(value) < 0 && currentNode.right != null) {
if (currentNode.right.val.compareTo(value) == 0) {
return currentNode;
}
currentNode = currentNode.right;
continue;
}
// follow the left branch (if possible)
if (currentNode.val.compareTo(value) > 0 && currentNode.left != null) {
if (currentNode.left.val.compareTo(value) == 0) {
return currentNode;
}
currentNode = currentNode.left;
continue;
}
break;
}

return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
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 {{{ public class ParentOFgivenChild { public static void main(String[] args) { new ParentOFgivenChild().run(); } //node class static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } //run public void run() { // build the simple tree from chapter 11. Node root = new Node(8); //System.out.println("Binary Tree Example"); //System.out.println("Building tree with root value " + root.value); insert(root, 6); insert(root, 10); insert(root, 7); insert(root, 5); insert(root, 4); insert(root, 8); insert(root, 9); insert(root, 12); // System.out.println("Traversing tree in order"); findParent(null, root); // printInOrder(root); /* System.out.println("After mirror image"); mirror_image(root); printInOrder(root); */ } public void insert(Node node, int value) { if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { /* System.out.println(" Inserted " + value + " to left of " + node.value);*/ node.left = new Node(value); } } else if (value > node.value) { if (node.right != null) { insert(node.right, value); } else { /* System.out.println(" Inserted " + value + " to right of " + node.value); */ node.right = new Node(value); } } } public int search(Node node,int value){ if(node.value==value) return node.value; if (node.value >value){ return search(node.left, value);} else{ return search(node.right, value);} } public void printInOrder(Node node) { if (node != null) { printInOrder(node.left); System.out.println( node.value); printInOrder(node.right); } } //using references of parent and child and call recursily for left and right subtree void findParent(Node parent,Node child){ if(child==null){} else{ if(child.value==8){if(parent==null){System.out.print(parent);}else{System.out.print(parent.value);}} else{ findParent(child, child.left); findParent(child, child.right); } } } } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done using PreOrder Traversal as shown below. capture the immediate ancestor when function stack is unwinding after having found the key

``````private boolean findParent(Node root, int x) {
if(root == null) return false;

if(root.data == x )return  true;

if(findParent(root.left,x) || findParent(root.right,x)){

System.out.print(root.data);
return false;
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static TreeNode findXParent(TreeNode root, int x){
if(root == null)return null;
if(root.value == x)return null;
while(!que.isEmpty()){
TreeNode temp = que.remove();
if(temp.left != null){
if(temp.left.data == x)return temp;
}
if(temp.right != null){
if(temp.right.data == x)return temp;
}

}
return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sweet PostOrder in Recursion C#

``````private int SearchResult { get; set; }
public void FindItsParent(BinaryTree<int> tree, int elementToBeFound, int Parent)
{
if (tree == null) return;

FindItsParent(tree.Left, elementToBeFound, tree.Node);
FindItsParent(tree.Right, elementToBeFound, tree.Node);
if (tree.Node == elementToBeFound)
{
SearchResult = Parent;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void findParent(node* n,int val,node* parent, int* parentValue){
if(n==NULL) return ;
if(n->val==val ){
*parentValue = parent->val;
}
findParent(n->left,val,n,parentValue);
findParent(n->right,val,n,parentValue);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void findParent(node* n,int val,node* parent, int* parentValue){
if(n==NULL) return ;
if(n->val==val ){
*parentValue = parent->val;
}
findParent(n->left,val,n,parentValue);
findParent(n->right,val,n,parentValue);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Node getParent(final Node root, final int data) {
Node found = null;
if (root != null) {
if (root.left != null) {
if (root.left.data == data) {
return root;
}
}
if (root.right != null) {
if (root.right.data == data) {
return root;
}
}

found = getParent(root.left, data);
if (found == null) {
found = getParent(root.right, data);
}
}
return found;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

static void findParent(Node node,
int val, int parent)
{
if (node == null)
return;

// If current node is the required node
if (node.data == val)
{

// Print its parent
System.out.print(parent);
}
else
{

// Recursive calls for the children
// of the current node
// Current node is now the new parent
findParent(node.left, val, node.data);
findParent(node.right, val, node.data);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void findParent(Node node,
int val, int parent)
{
if (node == null)
return;

// If current node is the required node
if (node.data == val)
{

// Print its parent
System.out.print(parent);
}
else
{

// Recursive calls for the children
// of the current node
// Current node is now the new parent
findParent(node.left, val, node.data);
findParent(node.right, val, node.data);
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````Node* returnParent(Node* root, int val)
{
if (!root)
return NULL;

if ((root->left != NULL && root->left->val == val) || (root->right != NULL && root->right->val == val))
return root;
else
{
Node* l = returnParent(root->left, val);
Node* r = returnParent(root->right, val);

if (l != NULL)
return l;
return r;

}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static int getParentVal(Tree t,int val, int x)
{
if(x>t.val)
{
checkParent(t.right,t.val,x);
}
else if(x<t.val)
{
checkParent(t.left,t.val,x);
}
else
{
return v;
}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.