Print all the paths in the tree

Print all the paths in the tree
foo(tree* root, int* arr, int idx)
{
if(!root) return;
arr[idx]=root->val;
if(!root->left&&!root->right){print arr; return;}//left node
foo(root->left,arr,idx+1);
foo(root->right,arr,idx+1);
}

Create a Circular Link List from a Given Binary Tree.

Create a Circular Link List from a Given Binary Tree.

struct node
{
 struct node* left;
 struct node* right;
 int data; 
}
typedef struct node* Node;

Node* B2L(node* root)
{
 if(!root) return NULL;
  
 Node* listA=B2L(root->left);
 Node* listB=B2L(root->right);
 return append(listA,root,listB);
}

Node* append(Node* listA, Node* root, Node* listB)
{
 if(listA)
  {
   root->next=listA;
   root->prev=listA->prev;
   listA->prev=root;
   root=listA;
  }

 if(listB)
  {
   Node* tail=listB->prev;
   root->prev->next=listB;//tail
   listB->prev->next=root;//tail
   listB->prev=root->prev;//head
   root->prev=tail;
  }
return root;
}

Convert a doubly linked list to a binary search tree in place. Think… Suppose the input list is 3 2 1 6 4 7 This is the way to convert sorted linked l

Convert a doubly linked list to a binary search tree in place. Think…
Suppose the input list is 3 2 1 6 4 7
list* foo(list* head)
{
if(!head) return NULL;
list* head1=head2=NULL;
findNewHead(head,head1,head2);
head->left=foo(head1);
head->right=foo(head2);
return head;
}

findNewHead(list* head, list*& head1, list*& head2)
{
if(!head->next) return;
if(head->val>head->next->val)
head1=head->next;
while(head->next)
{
if(head->val>head->next->val)
head=head->next;
else
{
head2=head->next;
head ->next=NULL;
head2->prev=NULL;
return;
}
}
return;
}

How do you perform binary search on a rotated sorted array? eg., 75, 77, 85, 91, 10, 19, 26, 29, 33,45, 67 I guess binary search will work. 75, 77, 85

How do you perform binary search on a rotated sorted array?
eg., 75, 77, 85, 91, 10, 19, 26, 29, 33,45, 67
I guess binary search will work.
75, 77, 85, 91, 10, 19, 26, 29, 33,45, 67
search first element which < 75,
while( low != high )
{
mid = ( low + high )/2
if( A[ mid ] > a[low] )
{
low = mid + 1;
}
else
{
pos = mid;//memory the position but do NOT break
high = mid;
}
}
//does not work for 3412
Or
Int f(int* a, int low, int up)
{
If(low+1=up) return up;
Int mid=(low+up)/2;
If(a[low]>=a[mid]) return f(a,low,mid);
Return f(a,mid,up);
}
//different from find median from two sorted array, where k is approaching to 1

Give n 32bit numbers which are all unsigned integers, then find the two numbers that can get the maximum value after their XOR. e.g. for these numbers

Give n 32bit numbers which are all unsigned integers, then find the two numbers that can get the maximum value after their XOR.
e.g.
for these numbers: 1, 2, 3, 4, 0xFFFFFFFE,
we should return 1 and 0xFFFFFFFE whose XOR result is the max.
please give a algorithm with time complexity <= nlgn, O(n)would be better.
I think this can be done in O(n).
I have a two-pass algorithm:

1. The first pass builds a binary tree.
. The tree has n leaves corresponding to the n given numbers.
. Each leaf has a depth of 32.
. When you add a leaf, you start from the MSB, if 0 go left, if 1 go right.
2. In the second pass, for each number x, bit complement (m=~x) it first, and then find the best "match" of m in the tree.
The "match" looks like the following:

  unsigned long BestMatch(unsigned long m, node * pRoot)  
  {
      unsigned long match = 0;
      for (int i=31; i>=0; i--)
      {
          match <<= 1;
          BYTE bit = (m>>i)&0x01;
          if (bit)
          {
              if (p->right)
              {
                  p = p->right;
                  match ++;
              }
              else
              {
                  p = p->left;
              }
          }
          else
          {
              if (p->left)
              {
                  p = p->left;
                  match ++;
              }
              else
              {
                  p = p->right;
              }
          }
      }
      return match;
  }

you are given a binary tree....write a code that returns the leaf node present at topmost level.... two leafs may be present at same level (take care

you are given a binary tree....write a code that returns the leaf node
present at topmost level....
two leafs may be present at same level
(take care of this condition)
use bfs
or

int lowleaf(node *root)
{
if(root==NULL) return 0;
else 
return 1+min(lowleaf(root->left),lowleaf(root->right));
}

Given a BST (Binary search Tree) how will you find median in that?

Given a BST (Binary search Tree) how will you find median in that?

Use two pointers p1 and p2
in order to traverse the tree
P1 forward 1 step, p2 forward 2 steps,
When p2 finish traversal, p1 point to the median
Or
Two pointers, p1 and p2
P1 traverse with left most in order
P2 traverse with right most in order
If p1 encounter p2, them point to median

Tree rotation

Tree rotation can be used to rebalance the tree, because the upon subtree decrease the height by one while the down subtree increase the height by one. The order of the tree will keep the same

Right rotation:
Tree* pivot=root->left;
root->left=Root->left->right;
pivot->right=root;
root=pivot;