## Facebook Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

Find the in-order successor of a node in a BST.

The first solution assumes each Node has a reference to its parent.

``````Node InOrderSucc(Node n) {

if (n == null)
return null; // or throw

// if there is a right child, the successor is the first element in an inorder traversal of that subtree
if (n.Right != null)
return LeftMostDescendant(n.Right);

// we must be the root, and without a right child, there is no successor
if (n.Parent == null)
return null;

// while n is a right child, it succedes its parent, so we go up
// if/when n is a left child, its parent will be its successor
// if we go up to the root without ever becoming a left child,
// it means the original n was the right-most element in the BST,
// and we will correctly return the root's parent - null
while (n.Parent.Right == n)
n = n.Parent;

return n;
}

private Node LeftMostDescendant(Node n) {
while (n.Left != null)
n = n.Left;
return n;
}``````

The second solution assumes that each node does not have a reference to its parent. and we are also given the root of the whole BST.

``````Node InOrderSucc(Node n, Node root) {
if (n == null)
return null; // or throw

// if there is a right child, the successor is the first element in an inorder traversal of that subtree
if (n.Right != null)
return LeftMostDescendant(n.Right);

var s = new Stack<Node>();
var m = root;

// find n, and push any node along the path to n onto the stack
while (m != null) {
if (m == n)
break;

s.push(m);
if m.Data < n.Data
m = m.Right;
else
m = m.Left;
}

// all n's parents are now on the stack

m = s.Peek() != null : s.Pop() : null;
while (m != null && n == m.Right) {
n = m;
m = s.Peek() != null ? s.Pop() : null;
}

return m;
}

private Node LeftMostDescendant(Node n) {
while (n.Left != null)
n = n.Left;
return n;
}``````

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

Time:O(n) space O(logn)-->in terms of stack frame(s).

``````public class Node
{
int value;
Node left;
Node right;
}

public class BSTService
{
public Node findInOrderSuccessor(Node n,Node key)
{
if(n==null)
{
throw new NullPointerException("input tree cannot be null");
}

if(n.value==key.value)
{
Node succesor=getLeftMostChild(n.right);
if(successor!=null)
{
return successor;
}
return n;

}
Node result;
if(key.value<n.value)
{
result=findInOrderSuccessor(n.left,key);
}else
{
result=findInOrderSuccessor(n.right,key);
}
if(result==null)
{
return null;
}
if(result.value==key.value)
{
result=n.value>key.value?n:result;
}
return result;
}

private Node getLeftMostChild(Node r)
{
if(r==null)
{
return null;
}
while(r.left!=null)
{
r=r.left;
}
return r;
}

}
}``````

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

This will not work when the key node doesn't have a right child. In those cases consider 2 different case. If the key is a left child then return its parent, else return its first parent whom you have reached by a left node.

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

Lets consider all cases:
1. If the node has a right child, then its logical descendant will be somewhere in the right tree. Therefore, find the minimum element that is bigger that the node in its right tree i.e. go right and then keep going left till you find a left node.
2. If the node has no right child, then
a) If the node is a right child of its parent, the in order traversal will end at the node, so no in order successor
b) If the node is a left child of its parent, then the parent is the in order successor.

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

Puneet for 2.a - we still can have inorder successor for this case - Make a BST for 5, 3, 4. Now find inorder successor of 4 will be 5 (parent's parent). Correct me if i am wrong.

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

You are wrong for 2. a). in that case you need to return the node's first parent such that the subtree that you were in is a left child of that parent.

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

Keep a stack, then iteratively, find the path from the head to the Node you are considering. Each node you visit, push onto the stack. Now, when u reach your target node, you will begin to pop from the stack. The first Node you pop from the stack that has a higher value than your target node is the inorder successor. If all of the nodes on the stack are smaller than the target node, your target node is the last Node in the inorder traversal so the next node after that must be null.

``````public Node findSuccessor(Node n, Node head, Stack s) {

while (true) {

if (current == null || current.value == n.value) {

break;
}

if (current.value < n.value) {

s.push(current);
current = current.right;
}

else if (current.value > n.value) {

s.push(current);
current = current.right;
}

}

while (s.size() > 0) {

if (s.peek().value > n.value) {

return s.peek();
}

s.pop();
}

return null;
}``````

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

my iterate way

``````public TreeNode findSuccessor(TreeNode root, TreeNode target) {
Stack<TreeNode> stack = new Stack<> ();
TreeNode cur = root ;
TreeNode pre = null ;
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur) ;
cur = cur.left ;
} else {
TreeNode mid = stack.pop() ;
if (pre == target) {
return mid ;
}
pre = mid ;
cur = pre.right ;
}
}
return null;
}``````

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

``````Inorder successor has two cases:
1. If the target node has right child then return minimum value from the right child node.
2. If the target node has no right child then we need to go from the root tree to the target node as one of the parent node will be the in-order successor of the target node.
There are two sub cases:
First is if the target node is the left child of the parent node and if parent node value is more than target node then we found the in order successor.
Second case is when target node is the right child of the parent node then in that case we should have kept the information about the ancestor of the parent node as that would be the in order successor of the target node. Obviously the parent node ancestor should have been the left child otherwise in-order successor will be NULL.No? Think about it for 2 min.``````

``````list *get_successor(list *head, list *node)
{
/* if node has right node get the minimum from the right node tree*/
if (node->right) {
return get_min(node->right);
} else{
/*get the parent node whose left child is the current node for which we are trying to find out the successor*/
list *successor = NULL;
while (node != current_node) {
if (node->data < current_node->data) {
successor = current_node;
current_node = current_node->left;
} else {
current_node = current_node->right;
}
}
return successor;
}
}``````

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

Here is the c++ solution of question.
I assumed I need to implement the method to find the successor for the given node in the tree.

``````struct Node{
int value;
Node * parent;
Node * left;
Node * right;
Node(int v):value(v), left(0), right(0), parent(0){}
};

Node * min(Node * n)
{
Node * cur = n;
while(cur->left)
{
cur = cur->left;
}
return cur;
}

Node * successor(Node *n)
{
if (n->right)
return min(n->right);
//find the parent.
Node *cur = n;
Node *p = n->parent;
while(p && p->right->value == cur->value)
{
cur = p;
p = cur->parent;
}
return p;
}

Node * find_successor(Node * root, int target)
{
Node * cur = root;
while(cur)
{
if (cur->value == target)
return successor(cur);
else if (cur->value > target)
cur = cur->left;
else
cur = cur->right;
}
return 0;
}``````

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

The solution in java

``````public class HelloWorld{

public static int findInOrderSuccessor(Node curr, int k)
{
int res = -1;

// Should return inOrder successor of an
// existing number in tree or any number?
// Can use foundk to decide
boolean foundk = false;
if (curr.data == k)
{
return curr.right.data;
}
while (curr != null)
{
if (k < curr.data)
{
// k is in the left subtree
res = curr.data;
curr = curr.left;
}
else if ( k > curr.data )
{
curr = curr.right;
}
else
{
foundk = true;
curr = curr.right;
}
}

return res;
}

public static void main(String []args){

Node root = new Node(10);
Node left1 = new Node(7);
Node left2 = new Node(5);
Node left3 = new Node(8);
Node left4 = new Node(9);
Node r1 = new Node(50);
Node r2 = new Node(60);
Node r3 = new Node(40);
Node r4 = new Node(55);

root.left = left1;
root.right = r1;
left1.left = left2;
left1.right = left3;
left3.right = left4;

r1.left = r3;
r1.right = r2;
r2.left = r4;

int result = findInOrderSuccessor(root, 9);

System.out.println("result = " + result);
}
}

public class Node
{
int data;
Node left;
Node right;

public Node(int data)
{
this.data = data;
}
}``````

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

1. if the current node has right child node, and if the right child node has left child node, return the leaf of the left most node. If the the right child node has no left child, return its value.
2. if the current node has no right child node, and if the current node is the left child of its parent, return its parent node's value (parent node can be null). If the current node is the right child node of its parent, set the parent node as the current node, and repeat (2).

``````public Node{
int value;
Node left;
Node right;
Node parent;
}
public Node findInOrderSuccessor(Node currentNode)
{
if(currentNode.right != null)
{
Node leftNode = currentNode.right.left;
if(leftNode  == null) return currentNode.right;
while(leftNode.left != null)
{
leftNode = leftNode.left;
}
return leftNode;
}
else if(currentNode.parent != null)
{
while(currentNode.parent != null)
{
if(currentNode.parent.left.value == currentNode.value)return currentNode.parent;
currentNode = currentNode.parent;
}

}
return null;
}``````

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

TEST

``````void TestCasesOfNextInOrder()
{
const std::vector<int> testInput{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);

auto nextInOrder = NextInOrder(rootBFS, 0);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootBFS, 1);
assert(*nextInOrder == 2);
nextInOrder = NextInOrder(rootBFS, 2);
assert(*nextInOrder == 3);
nextInOrder = NextInOrder(rootBFS, 3);
assert(*nextInOrder == 4);
nextInOrder = NextInOrder(rootBFS, 4);
assert(*nextInOrder == 5);
nextInOrder = NextInOrder(rootBFS, 5);
assert(*nextInOrder == 6);
nextInOrder = NextInOrder(rootBFS, 6);
assert(*nextInOrder == 7);
nextInOrder = NextInOrder(rootBFS, 7);
assert(*nextInOrder == 8);
nextInOrder = NextInOrder(rootBFS, 8);
assert(*nextInOrder == 9);
nextInOrder = NextInOrder(rootBFS, 9);
assert(*nextInOrder == 10);
nextInOrder = NextInOrder(rootBFS, 10);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootBFS, 11);
assert(nextInOrder == nullptr);

TreeNode<int>* rootDFS = ConstructTreeOnSortedValueDFS(testInput);
assert(rootDFS != nullptr);
nextInOrder = NextInOrder(rootDFS, 0);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootDFS, 1);
assert(*nextInOrder == 2);
nextInOrder = NextInOrder(rootDFS, 2);
assert(*nextInOrder == 3);
nextInOrder = NextInOrder(rootDFS, 3);
assert(*nextInOrder == 4);
nextInOrder = NextInOrder(rootDFS, 4);
assert(*nextInOrder == 5);
nextInOrder = NextInOrder(rootDFS, 5);
assert(*nextInOrder == 6);
nextInOrder = NextInOrder(rootDFS, 6);
assert(*nextInOrder == 7);
nextInOrder = NextInOrder(rootDFS, 7);
assert(*nextInOrder == 8);
nextInOrder = NextInOrder(rootDFS, 8);
assert(*nextInOrder == 9);
nextInOrder = NextInOrder(rootDFS, 9);
assert(*nextInOrder == 10);
nextInOrder = NextInOrder(rootDFS, 10);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootDFS, 11);
assert(nextInOrder == nullptr);

DeleteTree(&rootBFS);
DeleteTree(&rootDFS);
}``````

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

TEST

``````void TestCasesOfNextInOrder()
{
const std::vector<int> testInput{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);

auto nextInOrder = NextInOrder(rootBFS, 0);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootBFS, 1);
assert(*nextInOrder == 2);
nextInOrder = NextInOrder(rootBFS, 2);
assert(*nextInOrder == 3);
nextInOrder = NextInOrder(rootBFS, 3);
assert(*nextInOrder == 4);
nextInOrder = NextInOrder(rootBFS, 4);
assert(*nextInOrder == 5);
nextInOrder = NextInOrder(rootBFS, 5);
assert(*nextInOrder == 6);
nextInOrder = NextInOrder(rootBFS, 6);
assert(*nextInOrder == 7);
nextInOrder = NextInOrder(rootBFS, 7);
assert(*nextInOrder == 8);
nextInOrder = NextInOrder(rootBFS, 8);
assert(*nextInOrder == 9);
nextInOrder = NextInOrder(rootBFS, 9);
assert(*nextInOrder == 10);
nextInOrder = NextInOrder(rootBFS, 10);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootBFS, 11);
assert(nextInOrder == nullptr);

TreeNode<int>* rootDFS = ConstructTreeOnSortedValueDFS(testInput);
assert(rootDFS != nullptr);
nextInOrder = NextInOrder(rootDFS, 0);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootDFS, 1);
assert(*nextInOrder == 2);
nextInOrder = NextInOrder(rootDFS, 2);
assert(*nextInOrder == 3);
nextInOrder = NextInOrder(rootDFS, 3);
assert(*nextInOrder == 4);
nextInOrder = NextInOrder(rootDFS, 4);
assert(*nextInOrder == 5);
nextInOrder = NextInOrder(rootDFS, 5);
assert(*nextInOrder == 6);
nextInOrder = NextInOrder(rootDFS, 6);
assert(*nextInOrder == 7);
nextInOrder = NextInOrder(rootDFS, 7);
assert(*nextInOrder == 8);
nextInOrder = NextInOrder(rootDFS, 8);
assert(*nextInOrder == 9);
nextInOrder = NextInOrder(rootDFS, 9);
assert(*nextInOrder == 10);
nextInOrder = NextInOrder(rootDFS, 10);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootDFS, 11);
assert(nextInOrder == nullptr);

DeleteTree(&rootBFS);
DeleteTree(&rootDFS);
}``````

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

``````class BSTNode
{
int val;
BSTNode left;
BSTNode right;
BSTNode(int val)
{
this.val = val;
this.left = null;
this.right = null;
}
}

class InorderFlag
{
public boolean nodeFound = false;
InorderFlag(boolean val){
this.nodeFound = val;
}
}
class BSTree
{
BSTNode root;
boolean nodeFound = false;
BSTree()
{
this.root = null;
}

{
BSTNode nNode = new BSTNode(val);
}
private BSTNode AddNode(BSTNode root, BSTNode nNode)
{
if (root == null)
return nNode;

if(root.val < nNode.val)
if(root.val > nNode.val)

return root;

}
//public boolean RemoveNode(int val)
//    public boolean IsBST()
public void InOrderTraversal()
{

InOrderTraversal( root);
}
private void InOrderTraversal(BSTNode root)
{
if( root == null)
return;
InOrderTraversal( root.left);
System.out.println(root.val);
InOrderTraversal(root.right);
}

public BSTNode InOrderSuccessor(int a){

InorderFlag flag = new InorderFlag(false);
return  InOrderSuccessor( a, root, flag);
}

private BSTNode InOrderSuccessor(int a, BSTNode root, InorderFlag flag)
{
if( root == null)
return root;

BSTNode successor = InOrderSuccessor( a, root.left, flag);

if( successor != null)
return successor;

if( flag.nodeFound) {
System.out.println("Node found");
flag.nodeFound = false;
return root;
}

if( root.val == a) {
flag.nodeFound = true;
}

successor = InOrderSuccessor( a, root.right, flag);
if( successor != null)
return successor;

return null;
}
}

public class BST {
public static void main(String[] args) {
BSTree MyTree = new BSTree();
MyTree.InOrderTraversal();

System.out.println("Inorder successor");
System.out.println("9  " + (MyTree.InOrderSuccessor(9).val));
System.out.println("12  " + (MyTree.InOrderSuccessor(12).val));

// System.out.println("99  " + (MyTree.InOrderSuccessor(99).val));       // will give NPE as Inorder successor of 99 is null

}
}``````

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

``````class BSTNode
{
int val;
BSTNode left;
BSTNode right;
BSTNode(int val)
{
this.val = val;
this.left = null;
this.right = null;
}
}

class InorderFlag
{
public boolean nodeFound = false;
InorderFlag(boolean val){
this.nodeFound = val;
}
}
class BSTree
{
BSTNode root;
boolean nodeFound = false;
BSTree()
{
this.root = null;
}

{
BSTNode nNode = new BSTNode(val);
}
private BSTNode AddNode(BSTNode root, BSTNode nNode)
{
if (root == null)
return nNode;

if(root.val < nNode.val)
if(root.val > nNode.val)

return root;

}
//public boolean RemoveNode(int val)
//    public boolean IsBST()
public void InOrderTraversal()
{

InOrderTraversal( root);
}
private void InOrderTraversal(BSTNode root)
{
if( root == null)
return;
InOrderTraversal( root.left);
System.out.println(root.val);
InOrderTraversal(root.right);
}

public BSTNode InOrderSuccessor(int a){

InorderFlag flag = new InorderFlag(false);
return  InOrderSuccessor( a, root, flag);
}

private BSTNode InOrderSuccessor(int a, BSTNode root, InorderFlag flag)
{
if( root == null)
return root;

BSTNode successor = InOrderSuccessor( a, root.left, flag);

if( successor != null)
return successor;

if( flag.nodeFound) {
System.out.println("Node found");
flag.nodeFound = false;
return root;
}

if( root.val == a) {
flag.nodeFound = true;
}

successor = InOrderSuccessor( a, root.right, flag);
if( successor != null)
return successor;

return null;
}
}

public class BST {
public static void main(String[] args) {
BSTree MyTree = new BSTree();
MyTree.InOrderTraversal();

System.out.println("Inorder successor");
System.out.println("9  " + (MyTree.InOrderSuccessor(9).val));
System.out.println("12  " + (MyTree.InOrderSuccessor(12).val));

// System.out.println("99  " + (MyTree.InOrderSuccessor(99).val));       // will give NPE as Inorder successor of 99 is null

}``````

}

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

``````class BSTNode
{
int val;
BSTNode left;
BSTNode right;
BSTNode(int val)
{
this.val = val;
this.left = null;
this.right = null;
}
}

class InorderFlag
{
public boolean nodeFound = false;
InorderFlag(boolean val){
this.nodeFound = val;
}
}
class BSTree
{
BSTNode root;
boolean nodeFound = false;
BSTree()
{
this.root = null;
}

{
BSTNode nNode = new BSTNode(val);
}
private BSTNode AddNode(BSTNode root, BSTNode nNode)
{
if (root == null)
return nNode;

if(root.val < nNode.val)
if(root.val > nNode.val)

return root;

}
//public boolean RemoveNode(int val)
//    public boolean IsBST()
public void InOrderTraversal()
{

InOrderTraversal( root);
}
private void InOrderTraversal(BSTNode root)
{
if( root == null)
return;
InOrderTraversal( root.left);
System.out.println(root.val);
InOrderTraversal(root.right);
}

public BSTNode InOrderSuccessor(int a){

InorderFlag flag = new InorderFlag(false);
return  InOrderSuccessor( a, root, flag);
}

private BSTNode InOrderSuccessor(int a, BSTNode root, InorderFlag flag)
{
if( root == null)
return root;

BSTNode successor = InOrderSuccessor( a, root.left, flag);

if( successor != null)
return successor;

if( flag.nodeFound) {
System.out.println("Node found");
flag.nodeFound = false;
return root;
}

if( root.val == a) {
flag.nodeFound = true;
}

successor = InOrderSuccessor( a, root.right, flag);
if( successor != null)
return successor;

return null;
}
}

public class BST {
public static void main(String[] args) {
BSTree MyTree = new BSTree();
MyTree.InOrderTraversal();

System.out.println("Inorder successor");
System.out.println("9  " + (MyTree.InOrderSuccessor(9).val));
System.out.println("12  " + (MyTree.InOrderSuccessor(12).val));

// System.out.println("99  " + (MyTree.InOrderSuccessor(99).val));       // will give NPE as Inorder successor of 99 is null

}``````

}

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

``````Node inOrderSuccessor(Node focusNode) {
if (!focusNode) return null
if (focusNode.rightChild) {
focusNode.rightChild
}
else {
def parent = focusNode.parent
if (parent.leftChild == focusNode)
parent
else {
if (parent.parent.value > focusNode.value)
parent.parent
else null
}
}
}``````

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

``````Node inOrderSuccessor(Node focusNode) {
if (!focusNode) return null
if (focusNode.rightChild) {
focusNode.rightChild
}
else {
def parent = focusNode.parent
if (parent.leftChild == focusNode)
parent
else {
if (parent.parent.value > focusNode.value)
parent.parent
else null
}
}
}``````

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

This will be the left-most descendant of the right child of a specific node.

``````public class Node{
int value;
Node left, right;
}

public static Node successor(Node node){
if(node == null){
throw new NullPointerException();
}
if(node.right == null){
return null;
}
node = node.right;
while(node.left != null){
node = node.left;
}
return node;
}``````

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

if the target node("node") doesn't have a right child don't we have to return the first node whose value is greater than the target node? So if "node" is a left child we return its immediate parent. Otherwise, if "node" is a right child we return the first node in the path from root to "node" whose value is greater than that of "node".

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

If the specific node does not have a right descendant, and it itself is a left child, then its successor is its parent, not null.
Of course if the specific node is a right child and it has no right child itself, then we should return null.

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.