CareerCup

A very easy recursive solution without building the tree
#include<stdio.h>
#define max(x,y) x>y?x:y
int findlen(char a[],int *x)
{
if(a[*x]=='\0')
return 0;
(*x)++;
if(a[*x-1]=='L')
return 1;
int y=findlen(a,x),z=findlen(a,x);
return (1+(max(y,z)));
}
int main()
{
char a[]="PPPLLLPLL";
int x=0;
printf("depth of given tree=%d\n",findlen(a,&x));
return 0;
}

Following is the code in python.

def preorder_depth(my_str, cur_node_index, parent_depth, max_depth_sofar):
    if my_str[cur_node_index] == 'L':
        if max_depth_sofar < ( parent_depth + 1 ):
            max_depth_sofar = parent_depth + 1
        return (cur_node_index+1, max_depth_sofar)
    else:
        # left child
        (next_node_index, max_depth_sofar) = \
                   preorder_depth(my_str, cur_node_index+1, parent_depth+1, max_depth_sofar)
        # right child
        (next_node_index, max_depth_sofar) = \
                   preorder_depth(my_str, next_node_index, parent_depth+1, max_depth_sofar)

        return (next_node_index, max_depth_sofar)


## MAIN ##
print preorder_depth("PPPLLLL", 0, 0, 0)
print preorder_depth("PPPLPLLLL", 0, 0, 0)

The logic here is that in the given preorder traversal string, LL divides tree into two sub strees (left and right). The string which is left side of LL is represents left sub tree and right rest of the tree is right sub tree.

So, the depth of the tree is now Max(num of Ps in LST, 1 + num of Ps in RST) (+ 1 should be added to RST). Example:

P
P P
L L L P
L L

Preorder traversal string: PPLLPLPLL. Depth/height of LST is 2 and RST is 3. Finally, height of tree is 3.

public class DepthFinder {

	private int counter = 0;
	public int findDepth(char[] arr, int active, int depth) {
		if(counter >= arr.length)
			return depth;
		
		
		int i = counter++;
		if(arr[i] == 'P'){
			int dl = findDepth(arr, i, depth + 1);
			int dr = findDepth(arr, i, depth + 1);
			return (dl>dr)?dl:dr;
		}else{
			return depth;
		}
	}
}

Case; pplplpl
1) p
P p
L l p
L
2) p
P
L p
L p
L

Hr d depth differs. hence it cant b found. Corrrect if am wrong

Case; pplplpl
1) p
P p
L l p
L
2) p
P
L p
L p
L

Hr d depth differs. hence it cant b found. Corrrect if am wrong

Hi, would you please clarify is this tree balanced? With currently having requirements it's ambiguous how to rebuild a tree, consider the following string: "ppppllppll". There are 2 trees, that meet given requirements.

I am doubtful whether we can construct an unique tree by just having the preorder sequence. We will need inorder sequence here as well to construct a unique tree and hence the depth cannot be determined.

Simple solution, since each node can be complete or has to be a leaf
1.If value is P, add one to height and move ahead by one on string
2.If value is L and next value is P move ahead on string and dont add to height
3.If value is L and next value is L, move ahead on string and reduce height by 1
4.String will always end on LL, when this happens dont subtract 1 as we are not moving up
output the maximum value height attained during scan

int depth(string s,int& index)
{
if(index >= s.size()) {
return 0;
}
int rsl(0);
if(s[index] == 'P') {
int ld = depth(s,index+1);
int rd = depth(s,index+1);
rsl = 1 + max(ld,rd);
}
return rsl;
}

Isn't it possible to have multiple trees with same preorder traversal?

For example consider PPPPLLP

Both the below trees will have the above traversal, and they have different depths

P
    P      P
P     P
     L     L

Depth is 3

           P 
        P    P
     P
  P
L  L

Depth is 4