CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE-2s


Team: Hyderabad
Country: India
Interview Type: Phone Interview
More Questions from This 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;
}

- hnatsu January 18, 2017 | Flag Reply
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

- Nitish Garg January 20, 2017 | Flag Reply
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

- sumitgaur.iiita January 19, 2017 | Flag Reply
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);
        }
    }

- aurelian.lica January 26, 2017 | Flag Reply
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;
    }
    LinkedList<TreeNode<T>> queue = new LinkedList<>();
    queue.add(currentNode);

    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;
        }
        queue.add(currentNode.right);
      }
      // follow the left branch (if possible)
      if (currentNode.left != null) {
        if (currentNode.left.val.compareTo(value) == 0) {
          return currentNode;
        }
        queue.add(currentNode.left);
      }
    }

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

- Mike L February 04, 2017 | Flag Reply
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); } } } } }} - Harsh Bhardwaj February 15, 2017 | Flag Reply
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;
    }

- maxximus February 17, 2017 | Flag Reply
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;
            Queue<TreeNode> que = new LinkedList<TreeNode>();
            que.add(root);
            while(!que.isEmpty()){
                TreeNode temp = que.remove();
                if(temp.left != null){
                    if(temp.left.data == x)return temp;
                    que.add(temp.left);
                }
                if(temp.right != null){
                    if(temp.right.data == x)return temp;
                    que.add(temp.right);
                }
                
            
            }
            return null;
}

- mat February 23, 2017 | Flag Reply
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;
            }

}

- maksymas March 19, 2017 | Flag Reply
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);
}

- Pradeep Anumala March 24, 2017 | Flag Reply
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);
}

- Pradeep Anumala March 24, 2017 | Flag Reply
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;
  }

- Vishwaas May 24, 2017 | Flag Reply
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);
}
}

- Anonymous May 15, 2020 | Flag Reply
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); 
    } 
}

- Anonymous May 15, 2020 | Flag Reply
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;

	}
}

- Phoeniks January 18, 2017 | Flag Reply
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;
	}

}

- SS January 18, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More