Given a binary tree link all the right child of a node to their left siblings if present.

Given a binary tree link all the right child of a node to their left siblings if present.
foo(tree* root)
{
if(!root) return;
stl::queue s;
s.push(root);
while(!s.empty())
{
tree* curr=s.front();
s.pop();
if(curr->left&&curr->right)
connect curr->left to curr->right;
if(curr->left)
s.push(curr->left);
if(curr->right)
s.push(curr->right);
}
return;
}

check the binary tree is binary search tree

isBST2() Solution (C/C++)
/*
Returns true if the given tree is a binary search tree

*/
int isBST2(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a BST and its
values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);

// false if this node violates the min/max constraint
if (node->datadata>max) return(false);

// otherwise check the subtrees recursively,
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}

Given two nodes a and b, write a function that returns their closest 'parent' node (must have both a and b as 'children').

Given two nodes a and b, write a function that returns their closest 'parent' node (must have both a and b as 'children').

if u have O(n) space you can do it in O(n) run time
traverse preorder the addresses of the nodes and store it.
then traverse inorder the addresses of the nodes and store it.
eg tree
a
b c
d e f
have PreOrder:a b d e c f
Inorder: d b e a c f
for two node ptrs eg d and c
mark the positions in inorder array and find first preorder ptr which separates it into two
different parts of Inorder array
for above example first preorder ptr is a which separates inorder into dbe and cf
so a is first commom ancester of d and c

given a binary tree ,find the largest sub-tree which is a BST...(largest means subtree having largest no of nodes in it)...this is a wonderful questio

given a binary tree ,find the largest sub-tree which is a BST...(largest means subtree having largest no of nodes in it)

in order traverse the binary tree to keep the longest increasing substring

If there are two structs, TreeNode and Tree. TreeNode contains 3 elements, data, lChild and rChile. Tree contains 2 elements, int size and TreeNode *r

If there are two structs, TreeNode and Tree. TreeNode contains 3 elements, data, lChild and rChile. Tree contains 2 elements, int size and TreeNode *root. The tree is a complete tree. So how to find a O(logN) approach to insert a new node.

Notice this tree is complete, so the leaves level always toward left.
1 1
2 10
3 11
4 100
5 101
…
Just get binary of size, ignore the msb, from left to right scan bit by bit, 0 is go left, 1 is go right, until you finish the bits.

Given 2 nodes in a binary tree (not a binary search tree), find the first common parent node. You are not allowed to store any nodes in a data structu

Given 2 nodes in a binary tree (not a binary search tree), find the first common parent node. You are not allowed to store any nodes in a data structure.
Solution: find two heights, each of which from root to one node, get the difference (diff) of two heights, upward the node with longer height diff steps, then upward two nodes one step at each time, until you get the common node.

struct Tree{
 int val;
 struct Tree* p;
 struct Tree* l;
 struct Tree* r;
};
typedef struct Tree tree;


tree* foo(tree* root, tree* n1, tree* n2)
{
 if(!root||!n1||!n2) return NULL;
 int h1=h2=0;
 tree* c1=n1;
 tree* c2=n2;
 
 while(c1!=root)
 {
  h1++;
  c1=c1->p;
 }
 while(c2!=root)
 {
  h2++;
  c2=c2->p;
 }
 while(n1!=n2)
 {
  if(h1>h2){n1=n1->p;h1--;}
  else if(h2>h1){n2=n2->p;h2--;}
  else {n1=n1->p; n2=n2->p;h1--;h2--;}
 }
 return n1;
}

given any two nodes of a tree, you want to find if these two nodes has parent child relationship, how to do it in O(1) time and O(n) space

given any two nodes of a tree, you want to find if these two nodes has parent child relationship, how to do it in O(1) time and O(n) space

use pre-order to traverse the tree, for each node, record the start time and finish time, building a hash table for these recodes. if the time interval of one node includes the time interval of the second node, they have parent child relationship.

A tree without parent link, how to find out the path from a specific node to root

A tree without parent link, how to find out the path from a specific node to root

Use DFS (depth first search) to traverse the tree until the node is reached, ordering of the nodes in the stack is what we want.