CareerCup

Without further assumptions, this binary tree may be just a line with depth N. Hence, in such cases, each node has O(N) predecessors. So, just writing the results to the matrix uses O(N^2)

Not sure what it means by doing it better than in O(N^2). The number of array elements is O(N^2) and it takes at least O(N^2) steps to initialize the matrix. Also, is a node predecessor of itself?

Suppose the matrix was initialized with 0s. The next steps are to put 1s in it satisfying the above criterion.

Use recursion to solve this problem. During the unwinding of recursion -
1) If you are at the leaf node, do nothing.
2) else
2a. Copy 1s from the rows of left and right children
2b. Set M[currentNode][leftChild] = 1 and, M[currentNode][rightChild] = 1

I guess the O(n^2) constraint is on reading the binary tree i.e. don't read it n times. For filling up the array we do need O(n^2) time. Here is one approach
The predecessors of a node are the predecessors of its parent + its parent.
Using this logic we need to read the binary tree only once.
Tree traversal will be done as preorder.

XOR is full of him/herself.

First, "better than O(n^2)" is a meaningless statement! This shows a clear lack of understanding of what BigOh really means.

Repeat after me: BigOh is an UPPER F**K**G BOUND.

Assuming (s)he reallys mean "give an o(n^2) algorithm" (Yes, SmallOh, which is very different from BigOh), then (s)he wants us to fill an n^2 matrix, in o(n^2) time, which is impossible (unless you use some sparse matrix implementation where you pay the initialization cost on access, {yes, that is possible}).

XOR. LOL at ya.

Assuming the initial matrix is pre filed with -1 indicating no relationship. we will traverse and set the values.
two scenarios:
1) if its a balanced tree
The height of a balanced binary tree will be maximum logn. we can manage all the predecessors in a stack while doing a traversal(post order). the stack will contain the list of predecessors and for each n nodes there can be maximum logn predecessor. so time complexity is o(nlogn).
2) If its a non balanced tree, in that case worst case is that it can be a skewed tree or a linked list. In can of linked list we need to fill one diagonal half of the entire matrix. That itself is (n^2)/2 cells. Time complexity in that case will be o(n^2).

#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
  int data;
  Node *left;
  Node *right;
  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {

  }
};

void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else
  {
      return;//Already present key

  }
}


void Inorder(Node *root)
{
  if(root == NULL) return;

  Inorder(root->left);
  cout<<root->data<<"  ";
  Inorder(root->right);

}

void GetPrecessorder(Node* root,int **m,int &row, int &col)
{
   if(root == NULL)
   {
       return;
   }

   GetPrecessorder(root->left,m,row,col);

   if(row == -1)
   {
      row = root->data-1;
      m[row][col] = root->data;
      col++;
   }
   else
   {
      m[row][col++] = root->data;
   }
   GetPrecessorder(root->right,m,row,col);
}
void FillMatrix(Node* root, int**m, int n)
{
   if(root == NULL) return;
   int row = -1;
   int col = 0;
   //All precessorder are stored in one row that row not have any precessorder so finally we make that as 0
   GetPrecessorder(root,m,row,col);

   for(int i = 0; i < n; i++)
   {
      int r = m[row][i] -1;
      for(int j = i-1; j >= 0; --j)
      {
          int c = m[row][j] - 1;
          m[r][c] = 1;
      }
   }

   memset(m[row],0,sizeof(int)*n);
}
int main()
{
   Node *root = NULL;

   root = new Node(4,NULL,NULL);

   Node *a = root->left = new Node(1,NULL,NULL);
   Node *b = root->right = new Node(6,NULL,NULL);
   a->left = new Node(5,NULL,NULL);

   b->left = new Node(3,NULL,NULL);
   b->right = new Node(2,NULL,NULL);

   int n = 6;

   int**m = new int*[n];

   //O(n) Time complexity to fill all matrix elements as 0
   for(int i = 0; i < n; i++)
   {
      m[i] = new int[n];
      memset(m[i],0,sizeof(int)*n);
   }

   FillMatrix(root,m,n);

   for(int i = 0; i < 6; i++)
   {
      for(int j = 0; j < 6; j++)
      {
         cout<<m[i][j]<<"  ";
      }
      cout<<endl;
   }
   return 0;
}

I have 2 assumptions here:
The matrix is already filled with 0s.
The binary tree is full.

Represent the binary tree linearly in an array or a vector.
Calculate the predecessors recursively like this:

void getPredecessor(int start, int end)
{
	int mid = (start + end) / 2;
	for(int i=start; i<=end; i++)
	{
		predecessor[mid][i] = 1;
	}
	getPredecessor(start, mid-1);
	getPredecessor(mid+1, end);
}

public static void fillMatrix(Node node, List<Node> path)
	{
		if(node == null)
			return;
		
		for(int i = 0 ; i < path.size(); i++)
		{
			Node previous = path.get(i);
			M[previous.order][node.order] = 1;
		}
		path.add(node);
		
		ArrayList<Node> c1 = (ArrayList<Node>) ((ArrayList<Node>) path).clone();
		ArrayList<Node> c2 = (ArrayList<Node>) ((ArrayList<Node>) path).clone();
		
		fillMatrix(node.lchild, c1);
		fillMatrix(node.rchild, c2);
	}

question: How are we creating this array. What is 'i' and 'j' in arr[i][j] ? Each node in the tree has a number associated with it Or is the number based on some traversal ?

#include<stdio.h>
#include<stdlib.h>
struct node{
	int data;
	struct node *left;
	struct node* right;
};
int matrix[9][9];
struct node *newNode(int data){
	struct node *temp = (struct node*)malloc(sizeof(struct node));
	temp->data=data;
	temp->left=0;
	temp->right=0;
}
void binaryTreePathMatrix(struct node *root, int path[], int len){
	if(root==0)
		return;
	path[len]=root->data;
	len++;
		if(len>=2)
		pathPrintOrMatrixFill(path,len-1,root->data);
		binaryTreePathMatrix(root->left,path,len);
		binaryTreePathMatrix(root->right,path,len);
}
void pathPrintOrMatrixFill(int path[], int len, int data){
	int i;
	for(i=0;path[i]!=data;i++){
		printf("%d",path[i]);
		matrix[path[i]][data]=1;
	}
	printf("\n");
}
void main(){
	int path[10],i,j;
	struct node *root = (struct node *)malloc(sizeof(struct node));
	root=newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
	root->left->left->right=newNode(8);
	binaryTreePathMatrix(root,path,0);
	for(i=0;i<=8;i++){
		printf("\n");
		for(j=0;j<=8;j++){
			printf("%d  ",matrix[i][j]);
		}
	}
}

take an array of size n....populate it with the tree elements in BFS form but do not delete the elements......now start traversing the array from the end as such

while(i>0)
{
	M[arr[i]/2][arr[i]]=1;
	i--;

}

Is it a binary tree or a binary SEARCH tree? Predecessor has no meaning in the term of simple binary trees. (I think.)

In case of a binary search tree you can do an in-order traversal and fill the matrix in linear time assuming that are given a matrix initialized to all 0s by default.

This is done using dynamic programming

This can be done using dynamic programming

This can be done using dynamic programming

int i = 0, j=0, maxindex=0
Here, level of root is 0
Start traversing the tree level wise,starting from root

for 0<=j<n
arr[0][j]=1 //Root is predecessor of every node
arr[j][0]=0 //No node is the predecessor of root

Now since we are traversing level wise, we keep storing nodes which are at the same level in a queue ( Similar to a BFS is graph)
The largest index of the node at a level is stored in maxindex

Populating the matrix : so, once you have traversed the level, you have all the nodes at that level.
Start popping nodes. For every popped node i, make arr[i][j]=1 where j varies from maxindex+1 till n

This way, we traverse the tree once which takes O(n) since every node is just visited once.
The step of populating the matrix, at can take n-1 iterations for every node.

Thus order of solving this question is O(N^2)

1. In-order traverse binary tree, and get array of predecessors
2. Fill matrix using the array obtained in step 1
Complexity is O(2n).
Memory is O(n).

public class BinaryTreeNode
{
    public BinaryTreeNode Left;
    public BinaryTreeNode Right;
    public int Data;
}

public class BinaryTree
{
    public int Size;
    public BinaryTreeNode Root;
}

public static int[,] FinPredecessorsMatrix(BinaryTree binaryTree)
{
    var size = binaryTree.Size;
    var arr = new int[size];
    InOrderTraverse(binaryTree.Root, arr, 0);
    var matrix = new int[size, size];

    for (var i = 1; i < size; i++)
    {
        matrix[arr[i - 1], arr[i]] = 1;
    }

    return matrix;
}

private static int InOrderTraverse(BinaryTreeNode node, int[] arr, int index)
{
    if (node == null)
        return index;
    index = InOrderTraverse(node.Left, arr, index);
    arr[index] = node.Data;
    index++;
    return InOrderTraverse(node.Right, arr, index);
}

char p[133];
snprintf(p, sizeof(p), "This is a %.4s\n", "test
GARBAGE DATA");

But i am geting This is a 4s??????????????