CareerCup

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

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

- erika.r July 21, 2015 | Flag Reply
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;
	}
		
		
	}
}

- divm01986 July 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 05, 2015 | Flag
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.

- puneet.sohi July 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- skum July 23, 2015 | Flag
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.

- Anonymous August 05, 2015 | Flag
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) {

		Node current = head;

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

- SK July 20, 2015 | Flag Reply
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;
	}

- Scott July 21, 2015 | Flag Reply
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 *current_node = head;
                        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;
                }
        }

- aka July 21, 2015 | Flag Reply
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;
}

- hankm2004 July 22, 2015 | Flag Reply
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;
    }
}

- sanm July 26, 2015 | Flag Reply
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;
	}

- jiahuang August 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implementation: cpluspluslearning-petert.blogspot.co.uk/2015/09/bts-find-next-in-order-value-facebook.html

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

- undefined September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implementation: cpluspluslearning-petert.blogspot.co.uk/2015/09/bts-find-next-in-order-value-facebook.html

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

- peter tang September 16, 2015 | Flag Reply
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;
    }

    public void AddNode(int val)
    {
        BSTNode nNode = new BSTNode(val);
        this.root =  AddNode(root, nNode);
    }
    private BSTNode AddNode(BSTNode root, BSTNode nNode)
    {
        if (root == null)
            return nNode;

        if(root.val < nNode.val)
            root.right = AddNode(root.right, nNode);
        if(root.val > nNode.val)
            root.left = AddNode(root.left, nNode);

        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.AddNode(20);
        MyTree.AddNode(22);
        MyTree.AddNode(2);
        MyTree.AddNode(12);
        MyTree.AddNode(34);
        MyTree.AddNode(99);
        MyTree.AddNode(9);
        MyTree.AddNode(14);
        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


    }
}

- Anonymous September 28, 2015 | Flag Reply
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;
    }

    public void AddNode(int val)
    {
        BSTNode nNode = new BSTNode(val);
        this.root =  AddNode(root, nNode);
    }
    private BSTNode AddNode(BSTNode root, BSTNode nNode)
    {
        if (root == null)
            return nNode;

        if(root.val < nNode.val)
            root.right = AddNode(root.right, nNode);
        if(root.val > nNode.val)
            root.left = AddNode(root.left, nNode);

        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.AddNode(20);
        MyTree.AddNode(22);
        MyTree.AddNode(2);
        MyTree.AddNode(12);
        MyTree.AddNode(34);
        MyTree.AddNode(99);
        MyTree.AddNode(9);
        MyTree.AddNode(14);
        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


    }

}

- UD September 28, 2015 | Flag Reply
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;
    }

    public void AddNode(int val)
    {
        BSTNode nNode = new BSTNode(val);
        this.root =  AddNode(root, nNode);
    }
    private BSTNode AddNode(BSTNode root, BSTNode nNode)
    {
        if (root == null)
            return nNode;

        if(root.val < nNode.val)
            root.right = AddNode(root.right, nNode);
        if(root.val > nNode.val)
            root.left = AddNode(root.left, nNode);

        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.AddNode(20);
        MyTree.AddNode(22);
        MyTree.AddNode(2);
        MyTree.AddNode(12);
        MyTree.AddNode(34);
        MyTree.AddNode(99);
        MyTree.AddNode(9);
        MyTree.AddNode(14);
        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


    }

}

- UD September 28, 2015 | Flag Reply
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
            }
        }
    }

- Simona December 21, 2015 | Flag Reply
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
            }
        }
    }

- simona.valenti.0 December 21, 2015 | Flag Reply
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;
}

- zortlord July 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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".

- divm01986 July 20, 2015 | Flag
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.

- bvencel July 21, 2015 | Flag


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