Tree
Problem - 1: Implement "Binary Search" in less than two comparison?
BinarySearch(root, key):
if root == NULL then
return root
res = Root->Data - Key
if res == 0 then
return root
idx = (res >> (sizeof(Key) - 1)) & 1 //GET MSB which is 1 for -ve
Son[0] = Root -> Left;
Son[1] = Root -> Right;
return BinSearch(Son[idx], Key);
Problem - 2: For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree. So the tree...
2
/ \
1 3
Is changed to...
2
/ \
2 3
/ /
1 3
/
1
void doubleTree(struct node* node) {
struct node* oldLeft;
oldLeft = node->left;
node->left = newNode(node->data);
node->left->left = oldLeft;
}
Problem - 3: Given two trees, return true if they are structurally identical.
int sameTree(struct node* a, struct node* b) {
// 1. both empty -> true
if (a==NULL && b==NULL) return(true);
// 2. both non-empty -> compare them
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
sameTree(a->left, b->left) &&
sameTree(a->right, b->right)
);
}
// 3. one empty, one not -> false
else return(false);
}
Problem - 4: For the key values 1...numKeys, how many structurally unique binary search trees are possible that store those keys.Strategy: consider that each value could be the root.
Recursively find the size of the left and right subtrees.
int countTrees(int numKeys) {
}
}
Problem - 5: Change a tree so that the roles of the left and right pointers are swapped at every node. So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
void mirror(struct node* node) {
if (node==NULL) {
return;
}
else {
struct node* temp;
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
Problem - 6: Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work.
void printPaths(struct node* node) {
int path[1000];
void printArray(int ints[], int len) {
int i;
for (i=0; i
printf("%d ", ints[i]);
}
printf("\n");
}
Problem - 7: Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.
and check to see if the sum is 0 when you run out of tree.
int hasPathSum(struct node* node, int sum) {
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}
Problem - 8: Implement "level order search" for "Binary Tree"?This problem is same as "breadth first search" for "Binary Tree".
LevelOrder(Root):
Queue q
EnQueue(q,Root)
Loop if (q is not empty)
Node t = deQueue(q)
Visit(t)
if (it's left child is not NULL) then
EnQueue(leftChild)
if (it's right child is not NULL) then
EnQueue(rightChild)
EndLoopProblem - 9: Find Leaf node in a tree
FindLeafNodes(Tree *root)
{
if (root->left == NULL && root->right == NULL)
return 1;
else
return (FindLeafNodes(root->left) + FindLeafNodes(root->right))
}
Problem - 10: Height of a tree
#define max(x,y) ((x)>(y)?(x):(y))
int height(Tree T)
{
if(!T)
return -1;
else
return (1 + max(height(T->left), height(T->right)))
}
Problem - 11: No of nodes in a tree
int CountElements( Tree T )
{
if(!T)
return 0;
else
return (1 + CountElements(T->left) + CountElements(T->right));
}
Program - 12: Write a C program to delete a tree (i.e, free up its nodes)
Tree findMin( Tree T) // Recursively finding min element
{
if( !T )
return NULL;
else if( !T->left )
return T;
else
return findMin( T->left );
}
Tree DeleteTree( int x, Tree T) // To Delete whole tree recursively
{
if(!T)
{
DeleteTree(T->left);
DeleteTree(T->right);
free(T);
}
return NULL;
}
Tree DeleteNode( int x, Tree T ) // To Delete a Node with element x
{
Tree tmp;
if(!T)
return NULL;
else if( x < T->element )
T->left = DeleteNode( x, T->left );
else if( x > T->element )
T->right = DeleteNode( x, T->right );
else if( T->left && T->right )
{
tmp = findMin( T-> right );
T->element = tmp->element;
T->right = DeleteNode( T->element, T->right );
}
else
{
tmp = T;
if( T->left )
T = T->left;
else if( T->right )
T = T->right;
free(tmp);
}
}
Problem - 13: Write a C program to compute the maximum depth in a tree?
int maxDepth(struct node* node)
{
if (node==NULL)
{
return(0);
}
else
{
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
if (leftDepth > rightDepth) return(leftDepth+1);
else return(rightDepth+1);
}
}
Problem - 14: Function to add a new value to a Binary Search Tree
add(int value)
{
mynode *temp, *prev, *cur;
temp = malloc(sizeof(mynode));
temp->value = value;
temp->left = NULL;
temp->right = NULL;
if(root == NULL)
{
root = temp;
}
else
{
prev = NULL;
cur = root;
while(cur)
{
prev = cur;
cur = (value < cur->value)? cur->left : cur->right;
}
if(value > prev->value)
prev->right = temp;
else
prev->left = temp;
}
}
Problem - 15: Tree Traversal
Preorder Recursive:
void preorder(mynode *root)
{
if(root)
{
printf("[%d] ", root->value);
preorder(root->left);
preorder(root->right);
}
}
Preorder Iterative:
void iterativePreorder(mynode *root)
{
mynode *save[100];
int top = 0;
if (root == NULL)
{
return;
}
save[top++] = root;
while (top != 0)
{
root = save[--top];
printf("[%d] ", root->value);
if (root->right != NULL)
save[top++] = root->right;
if (root->left != NULL)
save[top++] = root->left;
}
}
Postorder Recursive :
void postorder(mynode *root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
printf("[%d] ", root->value);
}
}
Postorder Iterative:
void iterativePostorder(mynode *root)
{
struct
{
mynode *node;
unsigned vleft :1; // Visited left?
unsigned vright :1; // Visited right?
}save[100];
int top = 0;
save[top++].node = root;
while ( top != 0 )
{
/* Move to the left subtree if present and not visited */
if(root->left != NULL && !save[top].vleft)
{
save[top].vleft = 1;
save[top++].node = root;
root = root->left;
continue;
}
/* Move to the right subtree if present and not visited */
if(root->right != NULL && !save[top].vright )
{
save[top].vright = 1;
save[top++].node = root;
root = root->right;
continue;
}
printf("[%d] ", root->value);
/* Clean up the stack */
save[top].vleft = 0;
save[top].vright = 0;
/* Move up */
root = save[--top].node;
}
}
Inorder Recursive :
void inorder(mynode *root)
{
if(root)
{
inorder(root->left);
printf("[%d] ", root->value);
inorder(root->right);
}
}
Inorder Iterative :
void iterativeInorder (mynode *root)
{
mynode *save[100];
int top = 0;
while(root != NULL)
{
while (root != NULL)
{
if (root->right != NULL)
{
save[top++] = root->right;
}
save[top++] = root;
root = root->left;
}
root = save[--top];
while(top != 0 && root->right == NULL)
{
printf("[%d] ", root->value);
root = save[--top];
}
printf("[%d] ", root->value);
root = (top != 0) ? save[--top] : (mynode *) NULL;
}
}Problem - 16: A binary tree contain integer values (both positive and negative) in its data field. Given a number N, find a path from root to leaf which sums to N.
Problem - 17: Determine the largest common subtree (structurally) of two given binary trees T1 and T2, that is, the largest subtree of T1 that is structurally identical to a subtree in T2.
A .Contents of the nodes are irrelevant;
B. Content matters...A. We will have to modify the inorder tree traversal and put leaf as L and all inner node as p.....so after doing inorder traversal we will get the pattern interrms of L,P,(,) so find the longest common substring among the two trees traversals..this the one common structure.......
Problem - 19: Find the inorder successor and predecessor from a BST.struct node FindSuccessor(struct node X)
Problem - 20: Find two nodes in BST such that there sum is equal to X
Approach -1
1. Storing inorder in and array of n (and taking 2 pointers j=0,k=n-1)
if(a[j]+a[k]>sum)
k--;
else if ( a[j]+a[k]==sum) return (j,k);
else j++;Time complexity : O(n )
Space complexity : O(n)
Approach -2
a) Find the min element in the BST, say 'y'. Time complexity : O(log n )
b) z=x-y
c) do a binary search for z in BST. If it exists , here goes a pair.
d) Find the successor of y.
e) repeat steps b to d.Total Time complexity : O(n log n )
Total Space complexity : O(1), constant
Approach -3
a- Take one pointer pointing to minimum of BST. Time complexity : O(log n )
b - Take one pointer pointing to maximum of BST. Time complexity : O(log n )
c - If the sum is greater than SUM then go to predecessor of maximum node.
d - Else if sum is less than SUM then go to successor of minimum node.
while(max->data>min->data)
Common Ancestor for BST:Node getLCA_BST(Node root, Node x, Node y):
Node curr = root
while !(x < curr && curr < y): // x.value < curr.value
if curr < x && curr < y:
curr = curr.right
else: //x < curr && y < curr
curr = curr.left
return curr // assume x and y are in the tree
Common Ancestor for Binary Tree:class Node:
int value
Node left
Node right
Node parent
class ListNode:
Node value //Node is Binary Tree node
ListNode next
Node getLCA_BT(Node root, Node x, Node y):
ListNode lx = getPath(x) // Get list of path
ListNode ly = getPath(y) // Get list of path
return getLCAFromPaths(lx, ly) // find largest match
ListNode getPath(Node n):
ListNode ln = null
ListNode after = null
while (n != null):
ln = new ListNode()
ln.value = n
ln.next = after
after = ln
n = n.parent
return lnNode getLCAFromPaths(ListNode lx, ListNode ly):
Node lca = null
while (lx.value == ly.value): // lx.value.value
lca = lx.value //or ly.value
lx = lx.next
ly = ly.next
return lca
Problem - 22: Write a function that, given a binary search tree and a value, will find the next biggest node value in the tree
Problem - 23: Given a binary tree, write a program to find the maximum number and print its path from the root.
int maxsofar, maxpos; //global variables
Inorder(node *n, int position)
{
Inorder(n->left, position*2);
if(n->data > maxsofar)
{
maxsofar = n->data;
maxpos = position;
}
Inorder(n->right, position*2 + 1);
}
By the end of this traversal, you'll have the maximum value in "maxsofar", and the position encoded in an integer "maxpos".
If you don't have parent pointer support in tree node structure, You can print the path like below -
suppose the maxpos is 23,
1<-2<-5<-11<-23/2
root->left->right->right->right
Now to print the path of max value -
1. Array[(maxpos/2)+1]
2. i = 0
3. Loop while (maxpos > 1)
{
maxpos =/2
Array[i++] = maxpos
}
4. while (--i >= 0)
{
print (root->data)
if (i %2 == 0)
root = root->left;
else
root = root->right
}
Problem -24: Construct a "Doubly Link List" form a given "Tree".
void TreeToDlinklist(Tree* pNode): { Tree* pWalk;
if (pNode != NULL)
{
TreeToDlinklist(pNode->pLeft);
pWalk = node->pRight;
AppendToList(pNode);
TreeToDlinklist(pWalk);
}
}
BinarySearch(root, key):
if root == NULL then
return root
res = Root->Data - Key
if res == 0 then
return root
idx = (res >> (sizeof(Key) - 1)) & 1 //GET MSB which is 1 for -ve
Son[0] = Root -> Left;
Son[1] = Root -> Right;
return BinSearch(Son[idx], Key);
Problem - 2: For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree. So the tree...
2
/ \
1 3
Is changed to...
2
/ \
2 3
/ /
1 3
/
1
void doubleTree(struct node* node) {
struct node* oldLeft;
if (node==NULL) return;
// do the subtrees
doubleTree(node->left);
doubleTree(node->right);
// duplicate this node to its left doubleTree(node->left);
doubleTree(node->right);
oldLeft = node->left;
node->left = newNode(node->data);
node->left->left = oldLeft;
}
Problem - 3: Given two trees, return true if they are structurally identical.
int sameTree(struct node* a, struct node* b) {
// 1. both empty -> true
if (a==NULL && b==NULL) return(true);
// 2. both non-empty -> compare them
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
sameTree(a->left, b->left) &&
sameTree(a->right, b->right)
);
}
// 3. one empty, one not -> false
else return(false);
}
Problem - 4: For the key values 1...numKeys, how many structurally unique binary search trees are possible that store those keys.Strategy: consider that each value could be the root.
Recursively find the size of the left and right subtrees.
int countTrees(int numKeys) {
if (numKeys <=1) {
return(1);
}
else {
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...
int sum = 0;
int left, right, root;
return(1);
}
else {
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...
int sum = 0;
int left, right, root;
for (root=1; root<=numKeys; root++) {
left = countTrees(root - 1);
right = countTrees(numKeys - root);
left = countTrees(root - 1);
right = countTrees(numKeys - root);
// number of possible trees with this root == left*right
sum += left*right;
}
return(sum); sum += left*right;
}
}
}
Problem - 5: Change a tree so that the roles of the left and right pointers are swapped at every node. So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
void mirror(struct node* node) {
if (node==NULL) {
return;
}
else {
struct node* temp;
// do the subtrees
mirror(node->left);
mirror(node->right);
// swap the pointers in this node mirror(node->left);
mirror(node->right);
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
Problem - 6: Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work.
void printPaths(struct node* node) {
int path[1000];
printPathsRecur(node, path, 0);
}
}
/*
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.
*/
void printPathsRecur(struct node* node, int path[], int pathLen) {
if (node==NULL) return;
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.
*/
void printPathsRecur(struct node* node, int path[], int pathLen) {
if (node==NULL) return;
// append this node to the path array
path[pathLen] = node->data;
pathLen++;
path[pathLen] = node->data;
pathLen++;
// it's a leaf, so print the path that led to here
if (node->left==NULL && node->right==NULL) {
printArray(path, pathLen);
}
else {
// otherwise try both subtrees
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}
// Utility that prints out an array on a line. if (node->left==NULL && node->right==NULL) {
printArray(path, pathLen);
}
else {
// otherwise try both subtrees
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}
void printArray(int ints[], int len) {
int i;
for (i=0; i
printf("%d ", ints[i]);
}
printf("\n");
}
Problem - 7: Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.
and check to see if the sum is 0 when you run out of tree.
int hasPathSum(struct node* node, int sum) {
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}
Problem - 8: Implement "level order search" for "Binary Tree"?This problem is same as "breadth first search" for "Binary Tree".
LevelOrder(Root):
Queue q
EnQueue(q,Root)
Loop if (q is not empty)
Node t = deQueue(q)
Visit(t)
if (it's left child is not NULL) then
EnQueue(leftChild)
if (it's right child is not NULL) then
EnQueue(rightChild)
EndLoopProblem - 9: Find Leaf node in a tree
FindLeafNodes(Tree *root)
{
if (root->left == NULL && root->right == NULL)
return 1;
else
return (FindLeafNodes(root->left) + FindLeafNodes(root->right))
}
Problem - 10: Height of a tree
#define max(x,y) ((x)>(y)?(x):(y))
int height(Tree T)
{
if(!T)
return -1;
else
return (1 + max(height(T->left), height(T->right)))
}
Problem - 11: No of nodes in a tree
int CountElements( Tree T )
{
if(!T)
return 0;
else
return (1 + CountElements(T->left) + CountElements(T->right));
}
Program - 12: Write a C program to delete a tree (i.e, free up its nodes)
Tree findMin( Tree T) // Recursively finding min element
{
if( !T )
return NULL;
else if( !T->left )
return T;
else
return findMin( T->left );
}
Tree DeleteTree( int x, Tree T) // To Delete whole tree recursively
{
if(!T)
{
DeleteTree(T->left);
DeleteTree(T->right);
free(T);
}
return NULL;
}
Tree DeleteNode( int x, Tree T ) // To Delete a Node with element x
{
Tree tmp;
if(!T)
return NULL;
else if( x < T->element )
T->left = DeleteNode( x, T->left );
else if( x > T->element )
T->right = DeleteNode( x, T->right );
else if( T->left && T->right )
{
tmp = findMin( T-> right );
T->element = tmp->element;
T->right = DeleteNode( T->element, T->right );
}
else
{
tmp = T;
if( T->left )
T = T->left;
else if( T->right )
T = T->right;
free(tmp);
}
}
Problem - 13: Write a C program to compute the maximum depth in a tree?
int maxDepth(struct node* node)
{
if (node==NULL)
{
return(0);
}
else
{
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
if (leftDepth > rightDepth) return(leftDepth+1);
else return(rightDepth+1);
}
}
Problem - 14: Function to add a new value to a Binary Search Tree
add(int value)
{
mynode *temp, *prev, *cur;
temp = malloc(sizeof(mynode));
temp->value = value;
temp->left = NULL;
temp->right = NULL;
if(root == NULL)
{
root = temp;
}
else
{
prev = NULL;
cur = root;
while(cur)
{
prev = cur;
cur = (value < cur->value)? cur->left : cur->right;
}
if(value > prev->value)
prev->right = temp;
else
prev->left = temp;
}
}
Problem - 15: Tree Traversal
Preorder Recursive:
void preorder(mynode *root)
{
if(root)
{
printf("[%d] ", root->value);
preorder(root->left);
preorder(root->right);
}
}
Preorder Iterative:
void iterativePreorder(mynode *root)
{
mynode *save[100];
int top = 0;
if (root == NULL)
{
return;
}
save[top++] = root;
while (top != 0)
{
root = save[--top];
printf("[%d] ", root->value);
if (root->right != NULL)
save[top++] = root->right;
if (root->left != NULL)
save[top++] = root->left;
}
}
Postorder Recursive :
void postorder(mynode *root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
printf("[%d] ", root->value);
}
}
Postorder Iterative:
void iterativePostorder(mynode *root)
{
struct
{
mynode *node;
unsigned vleft :1; // Visited left?
unsigned vright :1; // Visited right?
}save[100];
int top = 0;
save[top++].node = root;
while ( top != 0 )
{
/* Move to the left subtree if present and not visited */
if(root->left != NULL && !save[top].vleft)
{
save[top].vleft = 1;
save[top++].node = root;
root = root->left;
continue;
}
/* Move to the right subtree if present and not visited */
if(root->right != NULL && !save[top].vright )
{
save[top].vright = 1;
save[top++].node = root;
root = root->right;
continue;
}
printf("[%d] ", root->value);
/* Clean up the stack */
save[top].vleft = 0;
save[top].vright = 0;
/* Move up */
root = save[--top].node;
}
}
Inorder Recursive :
void inorder(mynode *root)
{
if(root)
{
inorder(root->left);
printf("[%d] ", root->value);
inorder(root->right);
}
}
Inorder Iterative :
void iterativeInorder (mynode *root)
{
mynode *save[100];
int top = 0;
while(root != NULL)
{
while (root != NULL)
{
if (root->right != NULL)
{
save[top++] = root->right;
}
save[top++] = root;
root = root->left;
}
root = save[--top];
while(top != 0 && root->right == NULL)
{
printf("[%d] ", root->value);
root = save[--top];
}
printf("[%d] ", root->value);
root = (top != 0) ? save[--top] : (mynode *) NULL;
}
}Problem - 16: A binary tree contain integer values (both positive and negative) in its data field. Given a number N, find a path from root to leaf which sums to N.
Do iterative pre-order traversal, and keeping tab of sum of elements, we can easily determine if sum of elements from root to any of the leaves is equals to N.
bool ContainsSum(btree *root, int N)
{
if(!root)
return(N == 0)
else{
int remsum = N - root->value;
return((ContainsSum(root->left, remsum)) || (ContainsSum(root->right, remsum)));
}
if(!root)
return(N == 0)
else{
int remsum = N - root->value;
return((ContainsSum(root->left, remsum)) || (ContainsSum(root->right, remsum)));
}
Problem - 17: Determine the largest common subtree (structurally) of two given binary trees T1 and T2, that is, the largest subtree of T1 that is structurally identical to a subtree in T2.
A .Contents of the nodes are irrelevant;
B. Content matters...A. We will have to modify the inorder tree traversal and put leaf as L and all inner node as p.....so after doing inorder traversal we will get the pattern interrms of L,P,(,) so find the longest common substring among the two trees traversals..this the one common structure.......
Problem - 18: Given a binary tree with the following node structure
struct node
{
//data
//pointer to left subtree
//pointer to right subtree
//pointer to sibling
};
void link(node* root)struct node
{
//data
//pointer to left subtree
//pointer to right subtree
//pointer to sibling
};
The sibling pointers are NULL for all the nodes.Make the sibling pointers point to their respective nodes in O(n)time complexity
Nodes from same parent called siblings,If such a tree is given 2's sibling should point to 3 4's to 5, 6's to 7
1. Do BFS level order traversal
2. keeping a marker to mark the end of a 'level' - Here is is 'NULL'
3. Make a link with sblings
{
queue q;
node* cur = root;
if(root == NULL)
return;
queue
node* cur = root;
if(root == NULL)
return;
q.push(root);
q.push(NULL);
q.push(NULL);
while(Q.empty() == false)
{
root = Q.pop();
if(Q.empty() == false && root != NULL)
{
root.sibling = Q.front();
}
if(root)
{
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
if (cur->right) q.push(cur->right);
// since it is binary tree.. add marker
q.push(NULL);
}
}
Problem - 19: Find the inorder successor and predecessor from a BST.struct node FindSuccessor(struct node X)
{
if (X.right != NULL)
while ((Y != NULL) && (X == Y.right))
}
if (X.right != NULL)
{
return FindMinimumInBST(X.right);
}
Y = X.parent;return FindMinimumInBST(X.right);
}
while ((Y != NULL) && (X == Y.right))
{
X = Y;
Y = Y.parent;
}
return Y ;X = Y;
Y = Y.parent;
}
}
Problem - 20: Find two nodes in BST such that there sum is equal to X
Approach -1
1. Storing inorder in and array of n (and taking 2 pointers j=0,k=n-1)
if(a[j]+a[k]>sum)
k--;
else if ( a[j]+a[k]==sum) return (j,k);
else j++;Time complexity : O(n )
Space complexity : O(n)
Approach -2
a) Find the min element in the BST, say 'y'. Time complexity : O(log n )
b) z=x-y
c) do a binary search for z in BST. If it exists , here goes a pair.
d) Find the successor of y.
e) repeat steps b to d.Total Time complexity : O(n log n )
Total Space complexity : O(1), constant
Approach -3
a- Take one pointer pointing to minimum of BST. Time complexity : O(log n )
b - Take one pointer pointing to maximum of BST. Time complexity : O(log n )
c - If the sum is greater than SUM then go to predecessor of maximum node.
d - Else if sum is less than SUM then go to successor of minimum node.
while(max->data>min->data)
{
if(max->data+min->data == sum)
return(1);
else if(max->data+min->data>sum)
max = inorderpredecessor(max);
else
min = inordersucessor(min);
}
Problem - 21: Find common ancestor in a binary tree in less than O(n log n) in constant space?if(max->data+min->data == sum)
return(1);
else if(max->data+min->data>sum)
max = inorderpredecessor(max);
else
min = inordersucessor(min);
}
Common Ancestor for BST:Node getLCA_BST(Node root, Node x, Node y):
Node curr = root
while !(x < curr && curr < y): // x.value < curr.value
if curr < x && curr < y:
curr = curr.right
else: //x < curr && y < curr
curr = curr.left
return curr // assume x and y are in the tree
Common Ancestor for Binary Tree:class Node:
int value
Node left
Node right
Node parent
class ListNode:
Node value //Node is Binary Tree node
ListNode next
Node getLCA_BT(Node root, Node x, Node y):
ListNode lx = getPath(x) // Get list of path
ListNode ly = getPath(y) // Get list of path
return getLCAFromPaths(lx, ly) // find largest match
ListNode getPath(Node n):
ListNode ln = null
ListNode after = null
while (n != null):
ln = new ListNode()
ln.value = n
ln.next = after
after = ln
n = n.parent
return lnNode getLCAFromPaths(ListNode lx, ListNode ly):
Node lca = null
while (lx.value == ly.value): // lx.value.value
lca = lx.value //or ly.value
lx = lx.next
ly = ly.next
return lca
Problem - 22: Write a function that, given a binary search tree and a value, will find the next biggest node value in the tree
node* NextBigNode(node* root, int val)
{
if(!root)
return NULL;
if(!root)
return NULL;
node* nextBig = NULL;
node* cur = root;
node* cur = root;
while(cur)
{
// If value at current node is GREATER than value, then current could be the potential candidate for nextBig
// Go to the left subtree of current to see if there is another potential candidate for nextBig
if(cur->data > val)
// If value at current node is GREATER than value, then current could be the potential candidate for nextBig
// Go to the left subtree of current to see if there is another potential candidate for nextBig
if(cur->data > val)
{
nextBig = cur;
cur = cur-> left;
}
// If value at current node is LESS than value, then
// Go to the right subtree of current to see if there is another potential candidate for nextBig
elsenextBig = cur;
cur = cur-> left;
}
// If value at current node is LESS than value, then
// Go to the right subtree of current to see if there is another potential candidate for nextBig
{
cur = cur->right;
}
}cur = cur->right;
}
return nextBig;
}
}
Problem - 23: Given a binary tree, write a program to find the maximum number and print its path from the root.
int maxsofar, maxpos; //global variables
Inorder(node *n, int position)
{
Inorder(n->left, position*2);
if(n->data > maxsofar)
{
maxsofar = n->data;
maxpos = position;
}
Inorder(n->right, position*2 + 1);
}
By the end of this traversal, you'll have the maximum value in "maxsofar", and the position encoded in an integer "maxpos".
If you don't have parent pointer support in tree node structure, You can print the path like below -
suppose the maxpos is 23,
1<-2<-5<-11<-23/2
root->left->right->right->right
Now to print the path of max value -
1. Array[(maxpos/2)+1]
2. i = 0
3. Loop while (maxpos > 1)
{
maxpos =/2
Array[i++] = maxpos
}
4. while (--i >= 0)
{
print (root->data)
if (i %2 == 0)
root = root->left;
else
root = root->right
}
Problem -24: Construct a "Doubly Link List" form a given "Tree".
void TreeToDlinklist(Tree* pNode): { Tree* pWalk;
if (pNode != NULL)
{
TreeToDlinklist(pNode->pLeft);
pWalk = node->pRight;
AppendToList(pNode);
TreeToDlinklist(pWalk);
}
}
No comments:
Post a Comment