Dragon
BAN USERstuct node *constructTree(char *preorder, int *index)
{
// Return null if the array is empty
if (!preorder || *index == n)
return NULL;
// Create a node from the array at that index
struct node *new = NewNode(preorder[*index];
// If the node is a leaf node, terminate the funtion and return a pointer to that node
if (new->data == ‘L’)
return node;
// Move the index pointer ahead by one cell
*index = *index + 1;
// Construct the node's left pointer
new->left = constructTree(preorder, index);
// Move the index pointer ahead by one cell
*index = *index + 1;
// Construct the node's right pointer
new->right = constructTree(preorder, index);
// Return the current node's pointer to its caller funtion
return node;
}
Time Complexity O(n)
- Dragon March 08, 2012int matrix[N][N] = {0};
int main()
{
//Build a tree of n elements
int arr[N]; // This array is used to store paths from root to leaf
ancestorMatrix(root, arr, 0);
return 0;
}
void ancestorMatrix(struct node *root, int arr[], int level, int matrix[])
{
if (!root)
return;
for(int i = level - 1; i >= 0; i --)
matrix[root->data][result[i]] = 1; // The array contains all the predecessors of the current node
result[level++] = node->data; //Add your current node to the path array and send this array to its descendants
if (root->left)
ancestorMatrix(root->left, arr, level, matrix);
if (root->right)
ancestorMatrix(root->right, arr, level, matrix);
}
I think what the question means if - if you are given an infix/postfix expression, make an expression tree out of it.
Eg. Convert a postfix expression into an expression tree
Algorithm:
1. Intialize a stack to store binary tree nodes.
2. Read the array from left to right.
3. If you come across an operand, make a node out of it and push into the stack.
If its an operator, pop two nodes from the stack and first popped node would be the operator node's right child and the second popped node would be the operator node's left child. Push the operator node into the stack
4.The last popped node would be the head of the tree.
struct node *createTree(int a[])
{
Stack S;
struct node *new = NULL;
for(int i = 0; a[i]! = ‘\0’; i++)
{
if (arr[i] == ‘+’ || arr[i] == ‘-’ || arr[i] == ‘/’ || arr[i] == ‘*’)
{
new = newNode(a[i]);
new -> right = s1.pop();
new->left = s1.pop();
s1.push(new);
}
else
s1.push(newNode(a[i]);
}
}
return s1.pop();
}
//Use two reference pointers to store the maximum sum and the node that exposes the maximum sum in max and maxNode respectively
int maxSum(struct node *root, struct node **maxNode, int *max)
{
if (!root) return 0;
// If the node is leaf node, compare its value and return the value of that node
if(!root->left && !root->right)
{
if (node->val > max)
{ *max = root->value; max = &root; }
return root->val;
}
// Calculate the sum of the current node
int cmax = root->value + max(root->left, maxNode, max) + max(root->right, maxNode, max);
if (cmax > max)
{ *max = root->value; max = &root; } //Update the reference pointers
return cmax;
}
In order to reach the bottom, we gotta move RIGHT (q - 1) times and DOWN (p -1) times, so talking permutation, the number of unique combinations of result string would be ((p -1)! * (q - 1))! / (p - 1)! * (q - 1)! to compensate for the duplicates.
This is the logic behind this answer:
If there are n items and r of them are alike(nondistiguishable), the different no. of arrangements of these n items will be n! / r! where n!=1.2.3...n
For example if there are four letters A,B,C,D then different no. of arrangements will be
4!=1.2.3.4=24. But if two of them are alike, ie if the letters are A,A,B,C then the different no. of arrangements will be reduced to 4! / 2! because now no need to consider the internal arrangements of two A's.
In our case, we need a result that has q R's and p D's. Hence the answer.
And the code would be -
void reachBottom(str Matrix[], int level, int i, j, int p, int q)
{
if ( i == p && j == q)
cout<<matrix;
if ( i < p )
{
str[level++] = 'D';
reachBottom(str, level, i+1, j, p, q);
}
if ( j < q )
{
str[level++] = 'R';
reachBottom(str, level, i, j + 1, p, q);
}
}
- Dragon March 11, 2012