CareerCup

/**
 * Created by Majeed on 5/27/2014.
 */
public class BT {
    public BTNode root;

    // traverse reverse post-order and assign next to each
    // same logic can be used for pre-order and in-order
    // also this works for Binary and Binary Search both types of trees
    public static BTNode postOrderSuccessor(BTNode root, BTNode next) {
        if(root == null) return next;
        root.next = next;
        next = root;
        next = postOrderSuccessor(root.right, next);
        next = postOrderSuccessor(root.left, next);
        return next;
    }

    // utility to print post order successor of each node by traversing it preorder
    // fashion
    public static void preorder(BTNode root) {
        if(root == null) return;
        System.out.print(root.data + ":");
        if(root.next == null) System.out.print(null + " ");
        else System.out.print(root.next.data + " ");
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        BT tree = new BT();
        tree.root = new BTNode(1);
        tree.root.left = new BTNode(2);
        tree.root.right = new BTNode(3);

        tree.root.left.left = new BTNode(4);
        tree.root.left.right = new BTNode(5);

        tree.root.right.left = new BTNode(6);
        tree.root.right.right = new BTNode(7);

        BT.postOrderSuccessor(tree.root, null);
        BT.preorder(tree.root);
    }

    /*
     * output : (node:post-order successor)
     * 1:null 2:6 4:5 5:2 3:1 6:7 7:3
    */
}

FindNextNodeInOrder(Node root, Node node){
  // search the first in-order node in the right tree
  // because in in-order traverse, the left tree must
  // have been traversed before we reach the current node
  if(cur.right != null){
    Node cur = node.right;
    while(cur!= null){
      cur = cur.left;
    }
    
    return cur;
  }else{
  // if there is no right tree, we search for the first ancestor
  // who is a left child, this ancestor's parent will be the next
  // node we are looking for. Be careful since we may reach the root
  // without seeing any ancestor as a left child, in which case cur
  // will end up being null.
    cur = cur.parent;
    while(cur!= null && cur != cur.parent.left){
     cur = cur.parent;
    }
    
    if(cur!= null)
      return cur.parent;
    else  
      // no ancestor is a left child
      // it means the node in question itself is the last node
      // in the in-order traverse, there is no next node.
      return null;
  }
  
}

FindNextNodePreOrder(Node root, Node node){
   if(cur.left != null){
     return cur.left;
   }else if(cur.right != null){
     return cur.right
   }else{
    
      cur = cur.parent;
      // complex logic, the false conditions are either cur is null
      // or cur is left tree and it's right sibling is not null
      // the while loops says keeping searching if we haven't found
      // an ancestor who is a left child, or we found one but it's
      // right sibling is null
      while(cur!= null 
            && ((cur != cur.parent.left)
                ||(cur == cur.parent.left && cur.parent.right == null))){
       cur = cur.parent;
      }
      
      if(cur == null){
        return null;
      }else{
        return cur.right;
      }
   }
}

FindNextNodePostOrder(Node root, Node node){
  Node cur = node;
  if(cur.parent == null){
    return null;
  }
  
  if(cur = cur.parent.left){
    
    if(cur.parent.right != null){
      // search the left most node in the right sibling
      cur = cur.parent.right;
      while(cur.left != null){
        cur = cur.left;
      }
      
      return cur;
    }else{
      return cur.parent;
    }
  }else{
    return cur.parent;
  }
}

import java.util.*;

class logEntries{
	int startTime;
	int endTime;
	int RAMUsage;
	int id;
	logEntries(int startTime,int endTime, int RAMUsage,int id)
	{
		this.startTime=startTime;this.endTime=endTime;
		this.RAMUsage=RAMUsage;this.id=id;
	}
}
class entryNode
{
	int id;
	int time;
	int RAMUsage;
	entryNode(int id, int time, int RAMUsage)
	{
		this.id=id;
		this.time=time;
		this.RAMUsage=RAMUsage;
	}
}

public class peakRAM {
	
	public static Comparator<entryNode> entryComparator=new Comparator<entryNode>(){

		public int compare(entryNode n1, entryNode n2)
		{
			return (int)(Math.abs(n1.time)-Math.abs(n2.time));
		}
		
	};

	static int findPeakRam(ArrayList<logEntries> entries)
	{
		Queue<entryNode> entryPriorityQueue=new PriorityQueue<entryNode>(1,entryComparator);
		//Dividing the entries t
		for(logEntries en : entries)
		{
			entryPriorityQueue.add(new entryNode(en.id,en.startTime,en.RAMUsage));
			entryPriorityQueue.add(new entryNode(en.id,-en.endTime,en.RAMUsage));
		}
		//Polling the entries
		int Max=0,curr=0;
		while(true)
		{
			entryNode en=entryPriorityQueue.poll();

			if(en==null)
				break;
			//System.out.println("ID: "+en.id + " time : "+en.time + " RAMUsage : "+en.RAMUsage);
			if(en.time < 0)//
				curr-=en.RAMUsage;
			else 
			{
				curr+=en.RAMUsage;
				Max=Math.max(curr, Max);
			}
		}
		
		return Max;
	}
	public static void main(String[] args) {
		ArrayList<logEntries> entries=new ArrayList<logEntries>();
		entries.add(new logEntries(0, 100, 500, 1));
		entries.add(new logEntries(10, 70, 300, 2));
		entries.add(new logEntries(50, 200, 1000, 3));
		entries.add(new logEntries(110, 220, 400, 4));
		entries.add(new logEntries(175, 280, 750, 5));
		System.out.println(findPeakRam(entries));
		
	}

}

1) parent pointer is given.
- go to the parent of the current node.
- if current node is the right child of its parent => print parent.
- else return leftmost node of the right sub-tree of parent.

2) parent pointer is not given.
- traverse the tree and find the parent of the current node
- do the same as method (1).

Note that of current pointer is root than post-order successor if NULL (no post-order successor).

/* post order successor in binary tree
*/

#include<iostream>
using namespace std;

struct Node{
int data;
Node *left;
Node *right;
Node(int x): data(x), left(NULL), right(NULL) {}
};

Node *leftMostLeaf(Node *root){
while(root->left || root->right){
if(root->left) root = root->left;
else
root = root->right;
}
return root;
}

Node *postorderSuccessorRec(Node *root, int key, Node *parent, Node *treeroot){
//case 1: If current root is NULL, then succ is NULL
if(root == NULL)
return NULL;
//case 2: If current root is target node for which we are looking for successor
if(root->data == key){
//case 2.1: If current root is the root of the tree, succ is underfined.
if(root == treeroot)
return NULL;
//case 2.2: Otherwise, if current root is a right child, succ is parent.
else if(parent != NULL && parent->right == root)
return parent;
//case 2.3: otherwise current root is a left child and the following applies

//case 2.3.1: If the node has a right sibling, r, succ is the leftmost leaf in r's sub-tree
else if(parent != NULL && parent->left == root && parent->right != NULL)
return leftMostLeaf(parent->right);
//case 2.3.2: Otherwise succ is parent
else if(parent != NULL && parent->left == root && parent->right == NULL)
return parent;
//case 2.3.3: If none of above applies, then succ does not exist
else
return NULL;
}
//case 3: current root is not the target node for which we are looking successor
else{
//case 3.1: Search target node and its successor in left side of tree recursively, return if found
Node *left = postorderSuccessorRec(root->left, key, root, treeroot);
if(left)
return left;

//case 3.2: Search target node and its successor in right side of tree recursively, and return.
return postorderSuccessorRec(root->right, key, root, treeroot);
}
}

int main(){
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);

Node *succ;
succ = postorderSuccessorRec(root, 3, NULL, root);
cout<<succ->data<<endl;
}

// link-to-parent version
Node findNextNode(node n) {

	if (n == null)
		return null;

	// is there a right child?
	if (n.right != null) {

		n = n.right;

		// find the left-most node of the right branch
		while (n.left != null)
			n = n.left;

		return n;	
	}

    // no right node
    // find the first parent of a left node
	while (n.parent != null) {
		if (n == n.parent.left)
			return n.parent;
		n = n.parent;
	}

	return null;
}

// in-order traverse version - no link to parent
Node findNextNode(Node n, Node givenNode, BoolWrap nextIsIt) {

	if (n == null)
		return null;

	if (n.left != null)
		findNextNode(n.left, givenNode, nextIsIt);

	if (nextIsIt.val)
		return n;
	if (n == givenNode)
		nextIsIt.val = true;
	
	if (n.right != null)
		findNextNode(n.left, givenNode, nextIsIt);
}

class BoolWrap {
	boolean val;	
}

With parent is trivial. Without parent the idea is also simple - traverse the tree looking for the value and storing the smallest value which is greater than required.

void next(node* root, int & x)
	{
		if (root->value > x)
			x = min(x, root->value);
		if (root->value > x)
			find(root->left);
		else
			find(root->right);
	}