CareerCup

You are basically trying to find successor for that particular node. so go to right child and then extreme left child.if it's null then your right child is your next biggest element.

Assuming its a normal tree without parent pointers ...........

{
struct node *top[MAX_NODES];
struct node * next-biggerUtil(struct node *root,struct node *input,int *i){
if(root == NULL) return  NULL;
if(root == input )
{
int k;
for(k=*i-1; k >=0 && (top[k] ->right  &&  top[k]->right == input ) ;k--)
input= top[k];
if(k ==-1) return NULL;
return top[k];
return NULL;

}
top[*i++]=root;
if(root->data  > input ->data )
return next-biggerUtil(root->left,input,i);
return next-biggerUtil(root->right,input,i);
}



struct node * next-bigger(struct node * root,struct node * input){
if(root == NULL) return NULL;
if(input && input ->right ) return min(input->right); 
int i=0;
return next-biggerUtil(root,input,&i);
}

}

NextBiggest(Node Head, Node given)
{
while(head!= null)
{
if(given.val < head.val)
parent = head;
if(given.value == head.value)
return min(given);
}
return null;
}

min(Node given)
{
if(given.left != null)
return min(given.left)
return given;
}

Inorder traversal

We can take two variable those store the value for two contiguous values where we can check (node.value <variable1) else variable 2 is the value.

int BinaryTree::nextBiggest(int d){
	NodePtr ptr = root, parent = 0, grandparent;
	if(root == 0){
		return 0;
	}

	while(ptr != 0 && ptr->data != d){
		grandparent = parent;
		parent = ptr;
		if(d < ptr->data)
			ptr = ptr->left;
		else if(d > ptr->data)
			ptr = ptr->right;
	}

	if(ptr != 0){
		if(ptr->right != 0){
			ptr = ptr->right;
			while(ptr->left != 0)
				ptr = ptr->left;
		}
		else 
			ptr = grandparent;
		return ptr->data;
	}
	else
		return 0;

}

public Node nextLargerValueNode(Node root, int value){

if(root == null){
return null;
}
Node ancestor = null;
Node parent = null;
Node curr = root;

while(curr.value != value){
ancestor = parent;
parent = curr;
curr = (curr.value < value)? curr.right : curr.left;
}

if (curr!=null) {
if (curr.right != null) {
return curr.right;
} else {
return ancestor;
}
}
return null;
}

Solving the general case here is almost as easy as solving the specific case:

# Find the 2nd biggest by solving the general
# problem of finding the Nth largest element in a tree.
# The method is efficient, because it only traverses
# the left side of the tree when the right side
# has fewer than N-1 elements.

def test():
    tree123 = ((None, 1, None), 2, (None, 3, None))
    tree567 = ((None, 5, None), 6, (None, 7, None))
    tree = (tree123, 4, tree567)
    assert 6 == nth_element(tree, 2, 7) # second biggest
    assert 2 == nth_element(tree, 5, 6) # fifth biggest <= 6

def nth_element(tree, n, max):
    # Our inner function tries to return the nth largest
    # element <= max, but the tree might be too small, so we
    # also indicate the number of elements found.
    def nth_element_and_num_checked(tree, n):
        if tree is None:
            return None, 0
        left, val, right = tree
        if val > max:
            n_right = 0
        else:
            # For a big tree, we just recurse on the right tree.
            r_nth, n_right = nth_element_and_num_checked(right, n)
            if n_right == n:
                return r_nth, n
        if val <= max:
            n_right += 1
        # If the right side has exactly n-1 elements, the root
        # value is the solution.
        if n_right == n:
            return val, n
        # When we recurse to the left, we need to find a higher
        # ranking element than nth, depending on how many nodes
        # were on the right side.
        n_left = n - n_right
        result, n_left = nth_element_and_num_checked(left, n_left)
        return result, n_left + n_right
    result, num_checked = nth_element_and_num_checked(tree, n)
    if num_checked == n:
        return result
    else:
        raise Exception("tree too small")
    
test()

{
public class NextBiggerNode {

public static void main(String[] args){
NodeT root = new NodeT(5);
root.left = new NodeT(3);
root.right = new NodeT(8);
root.left.left = new NodeT(2);
root.left.right = new NodeT(4);
root.right.left = new NodeT(6);
root.right.right = new NodeT(10);
getNextBiggerNode(root, root.right.right);
}

private static void getNextBiggerNode(NodeT root, NodeT input) {
NodeT mainGrandParent = null;
NodeT parent = root;
NodeT ptr = root;
boolean isLeftElement = false;
while(ptr != null && ptr.data != input.data){
if(ptr.data > input.data){
mainGrandParent = parent;
parent = ptr;
ptr = ptr.left;
isLeftElement = true;
}else{
parent = ptr;
ptr = ptr.right;
isLeftElement = false;
}
}

if(ptr == null)
System.out.println("Not found");
else{
if(ptr.right != null){
ptr = ptr.right;
while(ptr.left != null)
ptr = ptr.left;
}else{
if(isLeftElement)
ptr = parent;
else
ptr = mainGrandParent;
}
if(ptr != null)
System.out.println(ptr.data+" found");
else
System.out.println("No next large element");
}
}

}
}

simple inorder() traversal will give it.

int NextBigger(node *root, int val)
{
static bool flag= false;

if(root==NULL)
return -1;

return NextBigger(root->left,val)
if(flag==true)
return root->data;
if(root->data==val)
flag=true;
return NextBigger(root->right);
}

C Solution with Tests:

The mildly fiddly part here is that a node's predecessor can be either a left child or a parent. Otherwise, it's basic recursion.

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

struct search_result {
    int found;
    int val;
};

struct tree {
    int val;
    struct tree *left;
    struct tree *right;
};

struct search_result biggest(struct tree *tree) {
    struct search_result sr;
    if (!tree) {
        sr.found = 0;
        return sr;
    }
    if (tree->right) return biggest(tree->right);
    sr.found = 1;
    sr.val = tree->val;
    return sr;
}

struct search_result successor(struct tree *tree, int val) {
    struct search_result sr_not_found;
    sr_not_found.found = 0;
    if (!tree) {
        return sr_not_found;
    }
    if (tree->val == val) {
        return biggest(tree->left);
    }
    if (tree->val < val) {
        if (!tree->right) return sr_not_found;
        if (tree->right->val == val && !tree->right->left) {
            if (tree->right->val != val) return sr_not_found;
            struct search_result sr;
            sr.found = 1;
            sr.found = 1;
            sr.val = tree->val;
            return sr;
        }
        return successor(tree->right, val);
    }
    else {
        return successor(tree->left, val);
    }
}

struct tree *make_node(int n) {
    struct tree *tree = malloc(sizeof(struct tree));
    tree->left = NULL;
    tree->right = NULL;
    tree->val = n;
    return tree;
}

int main(int argc, char **argv) {
    struct search_result sr;
    sr = successor(NULL, 3);
    assert(!sr.found);
    struct tree *t1 = make_node(1);
    struct tree *t2 = make_node(2);
    struct tree *t3 = make_node(3);
    struct tree *t4 = make_node(4);
    struct tree *t5 = make_node(5);
    struct tree *t6 = make_node(6);
    t2->left = t1;
    t2->right = t3;
    t4->left = t2;
    t4->right = t5;
    t5->right = t6;
    sr = successor(t1, 1);
    assert(!sr.found);
    sr = successor(t2, 2);
    assert(sr.found && sr.val == 1);
    sr = successor(t2, 3);
    assert(sr.found && sr.val == 2);
    sr = successor(t4, 5);
    assert(sr.found && sr.val == 4);
    sr = successor(t4, 4);
    assert(sr.found && sr.val == 3);
    sr = successor(t4, 3);
    assert(sr.found && sr.val == 2);
    return 0;
}

First call: fineNext(root,x,null)

public static Node findNext(Node n, int x, Node p) {
		if (n == null) return p;
		if (n.v > x) return findNext(n.l, x, n);
		return findNext(n.r, x, p);
	}

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std;
struct tree
{
int data;
struct tree *rc, *lc;
};
typedef struct tree tree;
tree *create(int d)
{
tree *temp;
temp=new tree;
temp->data=d;
temp->lc=temp->rc=NULL;
return temp;

}
tree *make(tree *root, int d)
{
if(root==NULL)
{
tree *temp;
temp=create(d);
return temp;
}
if(d<root->data)
{
root->lc=make(root->lc,d);
}
else if(d>root->data)
{
root->rc=make(root->rc,d);
}
return root;
}
void inorder(tree *root)
{
if(root==NULL)
return;
inorder(root->lc);
cout<<root->data<<" ";
inorder(root->rc);


}
void nextbig(tree *root, int n,int *ans)
{
if(root==NULL)
return;
if(root->data==n)
{
tree *temp;
if(root->rc)
{
tree *temp;
temp=root->rc;
while(temp->lc)
{
temp=temp->lc;
}
*ans=temp->data;
}
else
{
*ans=root->data;
}
return;
}

if(n<root->data)
{
nextbig(root->lc,n,ans);
if(*ans==n && root->data>n)
{
*ans=root->data;
}
}
else if(n>root->data)
{
nextbig(root->rc,n,ans);
if(*ans==n && root->data>n)
{
*ans=root->data;
}
}


}
int main()
{
int n,d;
tree *root=NULL;
cin>>n;
while(n--)
{
cin>>d;
root=make(root,d);
}

int x;
cout<<"Enter node whose next biggest you want to find\n";
cin>>x;
int ans;
nextbig(root,x,&ans);
if(ans!=x)
{
cout<<ans;
}
else
{
cout<<"Largest elemenn\n";
}
inorder(root);
}

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std;
struct tree
{
int data;
struct tree *rc, *lc;
};
typedef struct tree tree;
tree *create(int d)
{
tree *temp;
temp=new tree;
temp->data=d;
temp->lc=temp->rc=NULL;
return temp;

}
tree *make(tree *root, int d)
{
if(root==NULL)
{
tree *temp;
temp=create(d);
return temp;
}
if(d<root->data)
{
root->lc=make(root->lc,d);
}
else if(d>root->data)
{
root->rc=make(root->rc,d);
}
return root;
}
void inorder(tree *root)
{
if(root==NULL)
return;
inorder(root->lc);
cout<<root->data<<" ";
inorder(root->rc);


}
void nextbig(tree *root, int n,int *ans)
{
if(root==NULL)
return;
if(root->data==n)
{
tree *temp;
if(root->rc)
{
tree *temp;
temp=root->rc;
while(temp->lc)
{
temp=temp->lc;
}
*ans=temp->data;
}
else
{
*ans=root->data;
}
return;
}

if(n<root->data)
{
nextbig(root->lc,n,ans);
if(*ans==n && root->data>n)
{
*ans=root->data;
}
}
else if(n>root->data)
{
nextbig(root->rc,n,ans);
if(*ans==n && root->data>n)
{
*ans=root->data;
}
}


}
int main()
{
int n,d;
tree *root=NULL;
cin>>n;
while(n--)
{
cin>>d;
root=make(root,d);
}

int x;
cout<<"Enter node whose next biggest you want to find\n";
cin>>x;
int ans;
nextbig(root,x,&ans);
if(ans!=x)
{
cout<<ans;
}
else
{
cout<<"Largest elemenn\n";
}
inorder(root);
}

public int findNextLargestNode(BSTNode parent, BSTNode root,BSTNode search){

if(root=null){
	System.out.println("Data not found");
	return;
	}

if(search.getData()==root.getData()){
	if(root.getRight())
		return root.getRight().getData();
	else
		return parent.getData();
	
	
}
else if(search.getData()<root.getData())
	{
		parent=root;
		root=root.getLeft();
		findNextLargestNode(parent,root,search);
	
	}

else if(search.getData()>root.getData()){

	parent=root;
	root=root.getRight();
	findNextLargestNode(parent,root,search);

}
	
}

typedef struct Tree
{
int value;
Tree *right;
Tree *left;
}Tree;

int[] list;

void InOrder(Tree *root)
{
if(root != null)
{
InOrder(root->left);
list.Add(root->value);
InOrder(root->right);
}
}

void main()
{
int val = 0;
PrepareTree(Root);
printf("%d",list[len(list]-1));
}

Isnt it simply the parent of that node?