Google Interview Question
Site Reliability EngineersTeam: Google Engineering
Country: United States
Interview Type: Phone Interview
@Algos: Dude.. If all you are given is the pointer to a node, and the node only has a parent pointer, then it is impossible.
Even if you are given the root node, it is still impossible.
So shut it.
Assumption: Each node has information whether it is a left child or a right child.
Pre process the tree using a map. Set the left and right pointers which point to left and right child respectively. This is done in O(n).
If it is HAS a right child then the successor is the child.
else if it does not then the successor is the parent's parent.
If there are no left and right pointers in the node then use the map like this. key is the node whose parent, left right is in value.
<key, [parent, left, right]>.
buildMap(map, nodes[])
{
for(i=0; i<nodes.length; i++)
{
n = node[i];
map.put(n, null);
if(map.containsKey(n.parent))
{
if(n.isLeftChild())
map.get(n.parent).leftChild = n; // Assume map is of object references.
else
map.get(n.parent).rightChild = n;
}
}
}
* Complexity O(n)
public class BinarySearchTree {
static class Node{
Node left, right;
Node parent;
int data;
@Override
public String toString() {
return ""+data;
}
}
public static void main(String[] args) {
final Node node4 = new Node(){{left=null; right=null; parent=null; data=4;}};
final Node node8 = new Node(){{left=null; right=null; parent=null; data=8;}};
final Node node7 = new Node(){{left=node4; right=node8; parent=null; data=7;}};
node4.parent=node8.parent=node7;
final Node node18 = new Node(){{left=null; right=null; parent=null; data=18;}};
final Node node15 = new Node(){{left=null; right=node18; parent=null; data=15;}};
node18.parent=node15;
final Node root = new Node(){{left=node7; right=node15; parent=null; data=10;}};
node7.parent=node15.parent=root;
System.out.println(node4 + " : " + getInorderSuccessor(node4));
System.out.println(node8 + " : " + getInorderSuccessor(node8));
System.out.println(node7 + " : " + getInorderSuccessor(node7));
System.out.println(root + " : " + getInorderSuccessor(root));
System.out.println(node18 + " : " + getInorderSuccessor(node18));
System.out.println(node15 + " : " + getInorderSuccessor(node15));
}
public static Node getInorderSuccessor(Node node){
assert(node!=null);
if (node.right!=null){
return getLeftMost(node.right);
}
//node is left of parent
if (node == node.parent.left)
return node.parent;
//node is right of parent
return getParentWithRightBranch(node.parent);
}
private static Node getParentWithRightBranch(Node node) {
if (node.parent==null)
return null;
if (node.parent.left==node){
return node.parent;
}
return getParentWithRightBranch(node.parent);
}
private static Node getLeftMost(Node node) {
if (node.left==null)
return node;
return getLeftMost(node.left);
}
}
typedef struct TNode {
int key;
void* data;
TNode* left;
TNode* right;
TNode* parent;
};
TNode* inorder_successor(TNode* root, TNode* p) {
if( p && is_present_in_tree(root, p) ) {
if(p->right) {
return min_right_subtree(p->right);
} else {
TNode* X = p;
TNode* Y = p->parent;
while(Y && X==Y->right) {
X = Y;
Y = Y->parent;
}
return Y;
}
}else {
return NULL;
}
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class Find_Next_Node_InOrder_In_BinaryTree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
public static void createParentmap(Node head,HashMap<Node,Node> parentmap){
if(head==null){
System.out.println("This tree is empty!");
return ;
}
Queue<Node> nodeQueue=new LinkedList<Node>();
nodeQueue.add(head);
parentmap.put(head, null);
while(!nodeQueue.isEmpty()){
Node currentNode=nodeQueue.poll();
if(currentNode.left!=null){
parentmap.put(currentNode.left,currentNode);
nodeQueue.add(currentNode.left);
}
if(currentNode.right!=null){
parentmap.put(currentNode.right,currentNode);
nodeQueue.add(currentNode.right);
}
}
}
public static Node findNextNode(Node cur,HashMap<Node,Node> map){
if(!map.containsKey(cur)){
return null;
}
if(map.get(cur)==null||cur.right!=null){
return MostLeftNode(cur.right);
}
Node previous=map.get(cur);
Node current=cur;
while(previous.left!=current){
current=previous;
previous=map.get(previous);
if(previous==null){
return null;
}
}
return previous;
}
public static Node MostLeftNode(Node cur){
if(cur==null){
return null;
}
while(cur.left!=null){
cur=cur.left;
}
return cur;
}
public static void main(String[] args) {
Node head=new Node(16);
head.left=new Node(12);
head.right=new Node(18);
head.left.left=new Node(6);
head.left.right=new Node(14);
head.left.right.left=new Node(13);
head.left.right.right=new Node(15);
head.right.left=new Node(17);
head.right.right=new Node(24);
HashMap<Node,Node> parentMap= new HashMap<Node,Node>();
createParentmap(head, parentMap);
System.out.println(findNextNode(head.left.right,parentMap).value);
}
}
You can check my solution at github leafac/puzzles/tree/master/next-node:
class Node
attr_reader :value, :parent, :direction
def initialize(value, parent = nil, direction = nil)
@value = value
@parent = parent
@direction = direction
end
end
class NodeWithChildren
attr_reader :node
attr_accessor :left, :right
def initialize(node)
@node = node
end
end
class NextNodeResolver
def initialize(leafs)
@nexts = {}
nodes_to_process = leafs
nodes_processed_with_children = []
root = nil
until nodes_to_process.empty?
node_to_process = nodes_to_process.pop
node_to_process_with_children = NodeWithChildren.new(node_to_process)
nodes_processed_with_children.each do |node_processed_with_children|
if node_processed_with_children.node.parent == node_to_process
case node_processed_with_children.node.direction
when :left then node_to_process_with_children.left = node_processed_with_children
when :right then node_to_process_with_children.right = node_processed_with_children
end
end
end
if node_to_process.parent.nil?
root = node_to_process_with_children
elsif ! (nodes_to_process & nodes_processed_with_children.map(&:node)).include? node_to_process.parent
nodes_to_process << node_to_process.parent
end
nodes_processed_with_children << node_to_process_with_children
end
previous_node = nil
depth_first_seach = ->(node_with_children) do
unless node_with_children.nil?
depth_first_seach.(node_with_children.left)
@nexts[previous_node] = node_with_children.node unless previous_node.nil?
previous_node = node_with_children.node
depth_first_seach.(node_with_children.right)
end
end
depth_first_seach.(root)
end
def resolve(node)
@nexts[node]
end
end
Is there any restrictions I missed? Why don't we do it like below?
public Node getNext(Node root) {
if (root == null) return null;
if (root.right == null) return root.parent;
Node node = root.right;
while (node.left != null) {
node = node.left;
}
return node;
}
Node nextNode(Node node) {
if ( node == null ) { return null; }
if ( node.right != null ) {
node = node.right;
while ( node.left != null) {
node = node.left;
}
return node;
} else {
if ( node.parent == null) { // for root node parent == null;
return null;
} else if ( node.parent.left == node) { // it is parent's left node.
return node;
} else {
// node is the right child of parent and it has no right child.
Node currNode = node;
while ( node.parent != null ){ // current node is not root
node = node.parent;
if ( node.val > currNode.val) {
return node;
}
}
return null;
}
}
}
For a given node, if the node has right pointer not null, return the maximum in the right tree else return the first successor node for which given node lies in left subtree.
it'wrong, if the node has right child, return the right tree's min node value, else if the node has no father there's no next node, if it has father, and the node is father's left child then next node is father, else find father's father until the node is father's left child
Preorder Predecessor
package One;
public class PredecessorsNSuccessors {
public static void main(String[] args) {
BT root=new BT(1);
BT l=new BT(2);
BT r=new BT(3);
BT ll=new BT(4);
BT lr=new BT(5);
BT rl=new BT(6);
BT rr=new BT(7);
root.left=l; root.right=r; l.parent=r.parent=root;
l.left=ll; l.right=lr; ll.parent=lr.parent=l;
r.left=rl; r.right=rr; rl.parent=rr.parent=r;
BT.PreorderPredecessor(rr);
}
}
class BT{
int v;
BT parent;
BT left;
BT right;
public BT(int v)
{
this.v=v;
}
public static void PreorderPredecessor(BT node)
{
if(node==null)
{
System.out.println("The node id null");
return;
}
if(node.parent==null)
{
System.out.println("No PreorderPredecessor exists");
return;
}
if(node.parent.left==node)
{
System.out.println(node.parent.v);
return;
}
if(node.parent.right==node)
{
if(node.parent.left==null)
{
System.out.println(node.parent.v);
return;
}
BT temp=BT.getLastInPreorderTraversal(node.parent.left);
System.out.println(temp.v);
}
}
public static BT getLastInPreorderTraversal(BT node)
{
BT temp;
if(node.right!=null)
{
temp=getLastInPreorderTraversal(node.right);
}
else if(node.left!=null)
{
temp=getLastInPreorderTraversal(node.left);
}
else
{
temp=node;
}
return temp;
}
}
Preorder Successor
public static void PreorderSuccessor(BT node)
{
if(node.left!=null)
{
System.out.println(node.left.v);
return;
}
if(node.left==null && node.right!=null)
{
System.out.println(node.right.v);
return;
}
if(node.parent==null)
{
System.out.println("NO Successor");
return;
}
if(node.parent.left==node && node.parent.right!=null)
{
System.out.println(node.parent.right.v);
return;
}
BT child=node;
BT par=node.parent;
BT ps=BT.getPreSuc(child,par);
if(ps==null)
{
System.out.println("No Successor");
}
else
{
System.out.println(ps.v);
}
}
public static BT getPreSuc(BT child,BT par)
{
if(par==null)
{
return null;
}
if(par.left==child)
{
if(par.right!=null)
{
return par.right;
}
}
return getPreSuc(par,par.parent);
}
Inorder Predecessor
public static void InorderPredecessor(BT node)
{
if(node.left!=null)
{
node=node.left;
while(node.right!=null)
{
node=node.right;
}
System.out.println(node.v);
return;
}
while(node.parent!=null && node.parent.left==node)
{
node=node.parent;
}
if(node.parent!=null)
{
System.out.println(node.parent.v);
}
else
{
System.out.println("No Inorder Predecessor");
}
}
Inorder Successor
public static void InorderSuccessor(BT node)
{
if(node.right!=null)
{
node=node.right;
while(node.left!=null)
{
node=node.left;
}
System.out.println(node.v);
return;
}
while(node.parent!=null && node.parent.right==node)
{
node=node.parent;
}
if(node.parent!=null)
{
System.out.println(node.parent.v);
}
else
{
System.out.println("No Inorder Successor");
}
}
Postorder Predecessor
public static void PostorderPredecessor(BT node)
{
if(node.right!=null)
{
System.out.println(node.right.v);
return;
}
if(node.left!=null)
{
System.out.println(node.left.v);
return;
}
BT child=null;
while(node.parent!=null && (node.parent.left==null || node.parent.left==node))
{
child=node;
node=node.parent;
}
if(node.parent==null)
{
System.out.println("No Postorder Predecessor");
return;
}
else
{
System.out.println(node.parent.left.v);
return;
}
}
Postorder Successor
public static void PostorderSuccessor(BT node)
{
if(node.parent==null)
{
System.out.println("No Postorder Successor");
return;
}
if(node.parent.right==node)
{
System.out.println(node.parent.v);
return;
}
if(node.parent.right==null)
{
System.out.println(node.parent.v);
return;
}
BT temp=BT.getFirstInPostOrder(node.parent.right);
System.out.println(temp.v);
}
public static BT getFirstInPostOrder(BT node)
{
if(node.left!=null)
{
return getFirstInPostOrder(node.left);
}
if(node.right!=null)
{
return getFirstInPostOrder(node.right);
}
return node;
}
- Code Jockey September 25, 2012