Facebook Interview Question
SDE1sCountry: United States
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;
}
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)
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;
}
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;
}
'''
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:
print 'successor not found '
if __name__ == '__main__':
sys.exit(main())
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);
}
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.
- Marcello Ghali May 01, 2017However 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.