CareerCup

O( log n) complexity (assuming balanced), O(1) memory:

public static class Node{
    int val;
    Node left, right;
}

public static Node findNode(int val, Node node){
    while(node != null){
        if (val < node.val){
            node = node.left;
        }
        else if(val > node.val{
            node = node.right;
        }
        else{
            return node;
        }
    }
    return null;
}

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

Node * findNode (Node * root, int val)
{
if (root == NULL) return root;
if (root->val == val) return root;
Node * result = 0;
if (root->left != NULL)
{
result = findNode (root->left, val);
if (result != 0) return result;
}
if (root->right!=NULL)
{
result = findNode(root->right,val);
if (result != 0) return result;
}
return result;
}

#include<stdio.h>
#include<stdlib.h>
#include<process.h>
typedef struct tree
{
	int data;
	struct tree*lptr;
	struct tree*rptr;
}tree;
tree*create()
{
	tree*root,*t1,*temp,*prev;
	int val;
	char ch;
	root=NULL;
	printf("enter choice");
	fflush(stdin);
	scanf("%c",&ch);
	do
	{
		if(ch=='y')
		{
			t1=(tree*)malloc(sizeof(tree));
			printf("enter value");
			scanf("%d",&val);
			t1->data=val;
			t1->lptr=NULL;
			t1->rptr=NULL;
			if(root==NULL)
			{
				root=t1;
				temp=root;
			}
			else
			{  temp=root;
			   while(temp!=NULL)
			   {
			
				if(val<temp->data)
				{
					prev=temp;
					temp=temp->lptr;
				}
				    else if(val>temp->data)
				{
					prev=temp;
					temp=temp->rptr;
				}
				else
				{
					printf("duplicate data is not allowed");
				}
			   }
			   if(val<prev->data)
			   prev->lptr=t1;
			   else
			   prev->rptr=t1;
			}
		printf("do u want to have more nodes");
		fflush(stdin);
		scanf("%c",&ch);
	}
	}while(ch=='y');
	return(root);
}
tree* search(tree*root,int data)
{
	if(data==root->data)
	return(root);
	else if(data<root->data)
	return search(root->lptr,data);
	else if(data>root->data)
	return search(root->rptr,data);
	else
	return NULL;
}
int main()
{
	tree*root,*temp;
	int data,y;

	root=create();
		printf("enter data u want to search");
	scanf("%d",&data);
	temp=search(root,data);
	if(temp==NULL)
	printf("not found");
	else
	printf("found");
}

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

Node *findNode(Node *rootPtr, int data)
{
	if(rootPtr == NULL)	return rootPtr;
	if(rootPtr->data == data) return rootPtr;
	
	if(rootPtr->data > data)
		return findNode(rootPtr->left, data);
	if(rootPtr->data < data)
		return findNode(rootPtr->right, data);
}