## Facebook Interview Question for SDE1s

Country: United States

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

Since BinaryTree doesn't maintain any ordering properties for child nodes, worst case is in-order successor is the leaf node, which means we have to traverse the whole tree and find the next closest biggest element with O(n) complexity.
However we can try to optimize it and look for the node that have n.val+1 along the traversal, since n.val + 1 will be guaranteed the next successor, since there is no smaller int between n.val and v.val + 1.

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

We use an iterative inorder traversal. Once we find the needle, we return the next node in the inorder traversal.

``````TreeNode*
inOrderSuccessor(TreeNode* root, TreeNode* needle)
{
if(root == nullptr) return nullptr;
if(needle == nullptr) return nullptr;

std::vector<TreeNode*> stk;
bool found = false;
while(root != nullptr && !stk.empty()){
if(root != nullptr){
stk.push_back(root);
root = root->left;
} else {
root = stk.back();
stk.pop_back();
{
if(found){
return root;
}
if(root == needle){
found = true;
}
}
root = root->right;
}
}
return nullptr;
}``````

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

Language C#

``````public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val)
{
this.val = val;
}
}

public class Solution
{
public TreeNode inOrderSucccessor(TreeNode root, TreeNode input)
{
SuccessorTreeNode successorNode = null;
successorNode = inOrderSucccessor(root, input, successorNode);
}

private SuccessorTreeNode inOrderSucccessor(TreeNode root, TreeNode input, SuccessorTreeNode successorNode)
{
if(root == null)
{
return null;
}
SuccessorTreeNode node = inOrderSucccessor(root.left, input, successorNode);
if(node != null && node.isFound && node.successorNode == null)
{
node.successorNode = root;
return node;
}
else if(node != null && node.isFound)
{
return node;
}
if(root == input)
{
successorNode = new SuccessorTreeNode(true);
}
return inOrderSucccessor(root.right, input, successorNode);
}
}

public class SuccessorTreeNode
{
public TreeNode successorNode;
public bool isFound;
public SuccessorTreeNode()
{
isFound = false;
successorNode = null;
}
public SuccessorTreeNode(bool isFound)
{
this.isFound = isFound;
}
}``````

Complexity : O(N) + O(1)

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

Use stack for the inorder traversal iteratively.
if the key is found, set a boolean flag ,which can be used in the next iteration to return the value of the inorder successor

public Integer inOrderSuccessor(BTreeNode current,Integer key) {
Stack<BTreeNode> s1=new Stack<BTreeNode>();

boolean elementFound=false;
while(true) {

while(current!=null) {
s1.push(current);
current=current.left;
}
if(s1.isEmpty())break;
current=s1.pop();
if(elementFound) {
return current.data; //next element to the key
}
if(current.data==key) {
elementFound=true; //this boolean can be used in the next iteration
}

//System.out.print(current.data+" ");
current=current.right;

}
return null;
}

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

If the node has right child, the successor is the deepest left node, starting from the right child.
If the node doesn't have right child, we can get the path from root to to the node, and find the successor (iterating from the end of the path) as the first node which has left child.

``````class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};

vector<Node *> PathToNode(Node *root, Node *node)
{
class StackEntry {
public:
Node *node_;
int child_idx_;
StackEntry(Node *node, int child_idx)
{
node_ = node;
child_idx_ = child_idx;
}
};
vector<Node *> path;
if (root &&
node)
{
stack<StackEntry> st;
st.push(StackEntry(root, 0));
while (!st.empty()) {
StackEntry e = st.top();
st.pop();
if (e.node_) {
if (e.node_ == node) {
path.push_back(e.node_);
while (!st.empty()) {
path.push_back(st.top().node_);
st.pop();
}
return path;
}
if (e.child_idx_ == 0) {
st.push(StackEntry(e.node_, e.child_idx_ + 1));
st.push(StackEntry(e.node_->left_, 0));
} else if (e.child_idx_ == 1) {
st.push(StackEntry(e.node_, e.child_idx_ + 1));
st.push(StackEntry(e.node_->right_, 0));
}
}
}
}
return path;
}

Node *DeepestLeft(Node *node)
{
Node *n = node;
while (n &&
n->left_)
{
n = n->left_;
}
return n;
}

Node *GetInorderSuccessor(Node *root, Node *node)
{
if (root &&
node)
{
if (node->right_) {
return DeepestLeft(node->right_);
} else {
vector<Node *> path = PathToNode(root, node);
for (int i = 0; i + 1 < path.size(); ++i) {
if (path[i + 1]->left_ == path[i]) {
return path[i + 1];
}
}
}
}
return NULL;
}``````

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

``````'''
Given a Binary tree (Not binary Search Tree ), find the inorder successor of a node.
2
/ \
0    4
\  /  \
1 3   5

'''

import sys

class node :

def __init__(self, value):
self.value = value
self.left = None
self.right = None

def __str__(self):
l = r = ''
if self.left != None:
l += str(self.left)

result = str(self.value)

if self.right != None:
r += str(self.right)

return l + ' ' + result + ' ' + r

def createBTree(low, high):

if(low > high):
return None

mid = (low + high)/2
#print 'low: '+ str(low) + ' mid: '+str(mid) + ' high: '+ str(high)
n = node(mid)

n.left = createBTree(low, mid-1)
n.right = createBTree(mid+1, high)

return n

def findInOrderSuccessor(root, key, found):

l = r = None

if root.left :
l,found = findInOrderSuccessor(root.left, key, found)

if (found) :
return root, found

if (root.value == key):
found = True

if root.right:
r, found = findInOrderSuccessor(root.right, key, found)

if l :
return l, found
elif r :
return r, found
else :
return (None, found)

def main():
root = createBTree(0, 10)
print str(root)
key = 5
successor, found = findInOrderSuccessor(root, key, False)

if successor:
print 'successor for '+ str(key)+ ' is ' + str(successor.value)
else:
if __name__ == '__main__':
sys.exit(main())``````

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

``````Complexity = O(n)
public TreeNode inOrderSuccessor(TreeNode root, TreeNode n)  {
if(n.right != null) {
TreeNode ans = n;
while(ans.left!=null)ans = ans.left;
return ans;
}
return findParent(root, n);
}

public TreeNode findParent(TreeNode root, TreeNode n) {
if(root == null)return null;

if(root.left == n || root.right == n) return root;
TreeNode ans = findParent(root.left,n);
if(ans !=null)return ans;
return findParent(root.right,n);
}``````

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.