CareerCup

Node *findElement(Node *root, int n, int &num)
{
	if (root == NULL)
			return NULL;

	Node *left = findElement(root->left, n, num);
	if (left != NULL)
		return left;

	num++;
	if (n == num)
		return root;

	Node *right = findElement(root->right, n, num);

	return right;
}

code submitted:
public  class Result {
        Node foundNode;
        int iteration;
    }

    public  class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }

      
    }

public  void findNth(final Node node, int N, final Result result) {
        if (node.left != null && result.foundNode == null) {
            findNth(node.left, N, result);
        }

        // handle root
        result.iteration++;

        if (result.iteration == N) {
            result.foundNode = node;

            return;
        }

        if (node.right != null && result.foundNode == null) {
            findNth(node.right, N, result);
        }

How about this ?

inorder traversal of a binary tree prints elements in a sorted order .

So we can have a method that takes two arguments :the binary tree as an array and the integer n . Sort the the elements and output the Nth element in it?

node* findNthElementInorder(node *root,int n)
{
static int a;
static struct node *nthelement=NULL;

if(root==NULL)
return NULL;
if(nthelement==NULL)
{
nthelement=findNthElementInorder(root->left,n);
a++;
if(a==n)
return root;
nthelement=findNthElementInorder(root->right,n);
}
else
{
return nthelement;
}

}

use morris inorder traversal to get the required answer

or just use recursion

Untested recursive method

Tree *find(Tree *root, int n) {
    Tree *node
    int num = find(root, &node);
    if (num >= n) {
        return node;
    }
    return NULL;
}
   
int find(Tree * root,  int n, Tree ** needle) {
  
    if (!root) return 0;
    
    int num_left = find(root->right, n, needle);

    // Found in left subtree
    if (num_left >= n) return num_left;
   
    // The root is what we require
    if (num_left == n-1)  {*out  = root;  return n}
    
   int num_right = find(root->right, n-num_left, out);
   return num_right + 1 + num_left;
}

void fun(tnode root,int n){
if(root!=NULL){
if(n==1){
printf("%d",root->data);return;
}
else{
fun(root->left,n-1);
fun(root->right,n-1);
}
}
else{
printf("error");
return;
}
}

Tree is in ascending inorder traversal.

Here is a solution in java. The hard part of this algorithm is communicating the count of visited nodes between recursive calls. It would be trivial if there was some out-of-scope variable, but that is ugly and not needed. Java is pass by value, so using the primitive java int does not retain its value between recursive calls, however an Integer object wrapper will, because all we are doing is passing a copy of the reference to the integer object, which any recursive call can mutate.

Node findNthInOrderNode(Node root, Integer n){
    if(n < 0){ throw new IllegalArgumentException(); }
    if(root != null){
        Node left = findNthInOderNode(root.left(), n);
        if(left != null){ return left; }
        if(n == 0){ return root; }
        n--;
        Node right = findNthInOrderNode(root.right, n);
        if(right != null){ return right; }
    }
    return null;
}

void findNthElementInorder(struct TNode* node,int N, int& count, struct TNode*& nthNode) 
{
  assert(N>=0);
	if(node && count!=N) {
		if(nthNode==NULL) {
			findNthElementInorder(node->left, N, count, nthNode);
			
			// PROCESSED ONE ELEMENT INCREMENT THE COUNT
			count++;
      if(count==N) { nthNode = node; return; }
			
			findNthElementInorder(node->right, N, count, nthNode);
		}
	}
}

Node* f(Node* r, int *n)
{
    if(*n<0 || r==null)
      return null;

    if(*n==0)
      return r;
 
    Node* t = f(r->left, n);
    if(t)
      return t;
   
    if(*n==0)
       return r;

    *n = (*n)-1;
    return f(r->right, n);           
}

Here I am assuming that the answer can be stored in an argument variable passed into the input.

int func(Node* temp,int N,Node* ans = NULL){      
   if(temp==NULL)
      return 0;
   else{
      int ct = func(temp->left,N,ans);              
      if(ct >= N)                                                 
         return N;
      ct++;                                                         
      if(N-ct==0){                                             
          ans = temp;
          return N;
      }
      ct += func(temp->right,N-ct,ans);         
      if(ct >= N)
          return N;
      return ct;                                                 
  }
}

int inorderN(node * x, int &N)
{
if(N <=0)
error(‘N must be positive!’);
if(x==Null)
return -1;
N = N - 1;
if (N == 0)
return x->key;
int s = inorderN(x->left,N);
if (N == 0)
return s;
s = inorderN(x-right,N);
if (N == 0）
return s;

}

This is perfect for iterative inorder traversal which maintains the function signature and computes the function easily.

private static TreeNode findNthInOrderIterative(TreeNode root, int n) {
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode curr = root;
boolean done = false;
while (!done) {
if (curr != null) {
s.push(curr);
curr = curr.left;
}
else {
if(!s.empty()) {
curr = s.pop();
n--;
if(n == 0) {
return curr;
}
curr = curr.right;
}
else {
done = true;
}
}
}
System.out.println("Couldn't find element...returning the tree root");
return root;
}

Use modified recursive inorder

modified_inorder(node *pt,int n)
{
	if(pt!=NULL)
	{
	modified_inorder(pt->left,n);
	n--;
	if(n==0)
		cout << pt->info<<endl;
	modified_inorder(pt->right,n);
	}
}

void nthElement(Node *node, int &n, int &key)
{
if (node == NULL)
{
return;
}

nthElement(node->left, n, key);
n--;
if (n == 0)
{
key = node->v;
return;
}
nthElement(node->right, n, key);
}

Node *
Findnth( node * root, int n)
{
Stack<node *> stack;

While (root != null){
Stack.push(root);
Root = root.left;
}

While (!stack.empty() && n != 0)) {
Root = stack.top();
Stack.pop();
N--; // a node is getting visited.
If ( n == 0) return root;
// this node's left sub tree has been visited already, it itself has been visited as well. Now we need to concentrate on its right sub tree.
Root = root->right;
While (root != null) {
Stack.push(root);
Root = root->left;
}
}

memory O(n) and iterative. computation complexity equivalent to in order traversal.

#include <stdio.h>
#include <malloc.h>

class BinaryTreeNode
{
private:
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;

public:
BinaryTreeNode *FindNthInOrderNode(int n);
};
BinaryTreeNode *
BinaryTreeNode::FindNthInOrderNode(int n)
{
BinaryTreeNode **stack = (BinaryTreeNode **)malloc(n* sizeof(BinaryTreeNode *));
BinaryTreeNode *curr;
int stack_items = 0;
int add_position = 0;
int remain = n;

curr = this;
while (curr != NULL) {
stack[add_position] = curr;
curr = curr->left;
if (stack_items < n) {
stack_items++;
}
add_position = (add_position + 1) % n;
}

curr = NULL;
while (remain != 0 && stack_items != 0) {
/* POP */
--add_position;
--stack_items;
if (add_position < 0) {
add_position += n;
}
curr = stack[add_position];
if (--remain == 0) { // visiting current.
break;
}
curr = curr->right;
while (curr != NULL) {
stack[add_position] = curr;
curr = curr->left;
if (stack_items < n) {
stack_items++;
}
add_position = (add_position + 1) % n;
}
}

free(stack);
return curr;
}

def inorder_n( x, n )
	return 0,nil if x.nil?

	left,node = inorder_n( x.left, n )
	return left+1, node unless node.nil?
	n -= left

	return left+2,x if n == 0
	n -= 1

	right,node = inorder_n( x.right, n )
	return right+1, node unless node.nil?
	n -= right

	return n,nil
end



_,node = inorder_n( root, n)

morris inorder traversal.

TreeNode * InOrder(TreeNode * root, int n) {
  int cnt = 0;
  TreeNode * rs = NULL;
  while (root != NULL) {
    if (root->left != NULL) {
      cnt++;
      if (cnt == n) rs = root;
      root = root->left;
    } else {
      TreeNode * tmp = root->left;
      while (tmp->right != NULL && tmp->right != root) tmp = tmp->right;
      if (tmp->right == NULL) {
        tmp->right = root;
        root = root->left;
      } else {
        cnt++;
        if (cnt == n) rs = root;
        tmp->right = NULL;
        root = root->right;
      }
    }
  }
  return rs;
}

}

Solution with Swift.

/**
A function that takes 1 argument an integer N, it should return the N-th element in the inorder traversal of the binary tree.

- parameter n: The N-th element
*/

func findElement(n: Int) -> T? {

var num = n
return findElementHelper(root, n: &num)
}

private func findElementHelper(node: TreeNode<T>?, inout n: Int) -> T? {

guard let node = node else {
return nil
}

if let element = findElementHelper(node.left, n: &n) {
return element
}

if n == 0 {
return node.data
} else {
n = n-1
}

return findElementHelper(node.right, n: &n)
}