Linkedin Interview Question Software Engineer / Developers
Country: United States
It is a very nice idea, but what it returns is the *number of nodes* rather than the depth of the tree. However this nice idea can be used to first check if the tree presentation is valid or not. If not valid, return -1. Otherwise, count the number of '(' minus ')' at each location and take maximum.
We may use a stack to push "(" onto the stack and popping it off when we find a ")", tracking that it always represents a valid tree. Then, based on the max count of the stack that we see, we can determine the depth of the tree.
Need to also take care that there are only two child nodes. The above logic will not catch something like (00)(00)(00).
An interesting problem. Can be solved by recursion.
public static void main(String[] args) {
String s = "(00)";
System.out.println(find_dept(s,0,s.length()-1));
}
private static int find_dept(String s, int startIndex, int endIndex){
int split = getSplit(s,startIndex + 1, endIndex-1);
if (s.charAt(startIndex) == '(' && s.charAt(endIndex) == ')' && split > -1
&& (s.charAt(startIndex + 1) == '(' || s.charAt(startIndex + 1) == '0')
&& (s.charAt(endIndex - 1) == ')' || s.charAt(endIndex - 1) == '0')
&& startIndex < endIndex-2)
return 1 + Math.max(find_dept(s,startIndex+1,split), find_dept(s,split+1,endIndex-1));
else
return -1;
}
/**
* Find a potential for the recursive call
*/
private static int getSplit(String s, int startIndex, int endIndex) {
int c = 0;
int split = -1;
for (int i=startIndex;i<=endIndex;i++) {
if (s.charAt(i) == '(')
c++;
else if (s.charAt(i) == ')')
c--;
if (c == 0) {
split = i;
break;
}
}
return split;
}
SInce the question only asks for the depth and to determine whether the string is well formed, we only have to check whether the parentheses match and all chars other than '(' and ')' are '0', which can be done as follows:
int findDepth(String treeString) {
if (treeString == null || treeString.length() < 4) return -1;
char[] chars = treeString.toCharArray();
int depth = 0;
int maxdepth = 0;
for (int i = 0; i < chars.length; i++) {
char next = chars[i];
if (next == '(') {
depth++;
maxdepth = Math.max(depth, maxdepth);
} else if (next == ')') {
depth--;
} else if (next != '0') {
return -1; // an illegal character has been encountered
}
}
return (depth==0)?(maxdepth-1):-1; // not well-formed unless
parentheses match (depth=0)
}
Nope, you are correct. Should have stuck with the first idea; a simple recursive descent parser, that would have caught those cases
well, i think this method is still doable. just need to check # of 0 at the end.
public class stringBinaryTree {
public static int findDepth( String s )
{
int countLeft = 0;
int countLeftTotal = 0;
int countZero = 0;
int depth = -1; // countLeft - 1
for( int i = 0; i < s.length(); i++)
{
char a = s.charAt( i );
switch( a ){
case '0': countZero++; break;
case '(': { countLeft++; countLeftTotal++; }; break;
case ')': { if( depth < countLeft - 1 )
depth = countLeft - 1;
countLeft = 1;
};break;
default: return -1;
}
/* if( a == '(' )
countLeft++;
else if( a == ')' && depth < ( countLeft - 1 ) )
{
depth = countLeft - 1;
countLeft = 1;
}
else if( a != '0' )
return -1;*/
}
if( countZero == countLeftTotal + 1 )
return depth;
else
return -1;
}
/**
* @param args
*/
public static void main(String[] args) {
String s1 = "(00)"; //0
String s2 = "((00)0)"; // 1
String s3 = "((00)(00))"; // 1
String s4 = "((00)(0(00)))"; // -> 2
String s5 = "((00)(0(0(00))))"; // -> 3
String s6 = "x"; // -> -1
String s7 = "0"; // -> -1
String s8 = "()"; // -> -1
String s9 = "(0)"; // -> -1
String s10 = "(00)x"; // -> -1
String s11 = "(0p)"; // -> -1*/
System.out.println( findDepth(s1));
System.out.println( findDepth(s2));
System.out.println( findDepth(s3));
System.out.println( findDepth(s4));
System.out.println( findDepth(s5));
System.out.println( findDepth(s6));
System.out.println( findDepth(s7));
System.out.println( findDepth(s8));
System.out.println( findDepth(s9));
System.out.println( findDepth(s10));
System.out.println( findDepth(s11));
}
}
int get_depth(char ** cur)
{
int ld = 0, rd = 0, depth = 0;
if(**cur == NULL)
return 0;
switch(**cur)
{
case '(':
(*cur)++;
// process left node
ld = get_depth(cur);
// process right node
rd = get_depth(cur);
if(**cur == ')' && ld != -1 && rd != -1)
{
(*cur)++;
if(ld > rd)
return ld+1;
else
return rd+1;
}
else return -1;
case '0':
(*cur)++;
return 0;
default:
return -1;
}
}
int find_depth (char * k)
{
char * tmp = k;
int depth = get_depth(&tmp);
if(depth != -1)
depth--;
if(*tmp != NULL)
depth = -1;
return depth;
}
void main()
{
// char* str = "((00)(0(0(00))))";
// char* str = "(0)";
// char* str = "(00)";
char* str = "(00)x";
printf("depth for %s: %d\n", str, find_depth(str));
}
Recursive Implementation in Python
"""
Synopsis:
Check the well-formedness at each level
- Recursively call for each child node (if it's found)
Example:
((00)(0(0(00)))) # returns 3
(00)x # returns -1
"""
# Return depth of tree if it's well-formed
# @param input : input string
# @param depth : current depth
# @return : depth of tree (if well-formed)
def paren_tree(input, depth = 0):
print "[paren_tree] "+input
if input == "(00)":
return depth
elif input[0] != "(" or input[-1] != ")":
return -1
# Only left or right child
elif input[1] == "(" and input[-2] == "0":
return paren_tree(input[1:-2], depth + 1)
elif input[1] == "0" and input[-2] == ")":
return paren_tree(input[2:-1], depth + 1)
# Both left and right child
elif input[1] == "(" and input[-2] == ")":
lchild, rchild = split_children(input[1:-1])
ldepth, rdepth = paren_tree(lchild, depth+1), paren_tree(rchild, depth+1)
if ldepth > 0 and rdepth > 0:
return max(ldepth, rdepth)
else:
return -1
else:
return -1
# Split two instances of paren_tree
def split_children(input):
count_lp, count_rp = 1, 0
i = 1
while count_lp > count_rp:
if input[i] == "(":
count_lp += 1
elif input[i] == ")":
count_rp += 1
i += 1
print "[split_children] ",input[:i], input[i:]
return [input[:i], input[i:]]
print paren_tree("((00)(0(0(00))))")
print paren_tree("((00)(0(0(000))))")
public int find_depth(String tree) {
if(tree == null || tree.length() < 4 || tree.charAt(0) != '(') {
return -1;
}
int height = -1;
int lengthOfString = tree.length();
int isBalanced = 0;
int countZeros = 0;
for(int i = 0 ; i < lengthOfString; i++) {
char c = tree.charAt(i);
if(c == '0' || c == '(' || c == ')') {
if( c == '(' ) {
isBalanced++;
} else if ( c == ')') {
isBalanced--;
} else {
countZeros++;
}
} else {
return -1;
}
}
boolean value = hasRoot(tree);
if(isBalanced == 0 && countZeros >= 2 && value) {
if(tree.matches("\\(\\(00\\)0\\)")) {
return 1;
}
// find number of "(0" and return count -1 as dept.
Pattern pattern = Pattern.compile("\\(0");
Matcher matcher = pattern.matcher(tree);
while(matcher.find()) {
height++;
}
}
return height;
}
private boolean hasRoot(String str) {
// Find if it contains following sequence.
return str.contains("(00)");
}
Some additional case it will cater.
find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1
Some additional case it will cater.
find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1
Some additional case it will cater.
find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1
Some additional case it will cater.
find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1
Some additional case it will cater.
find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1
Some additional case it will cater.
find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1
Some additional case it will cater.
find_depth(')(') -> -1
find_depth(')0(') -> -1
find_depth(')(00)(') -> -1
find_depth('((00000))') -> -1
int find_depth(char *str)
{
int depth = -1;
char *curr = str;
try
{
expectopen(&curr);
expectchild(&curr, &depth);
expectchild(&curr, &depth);
expectclose(&curr)
depth++;
catch (exception)
{
return -1;
}
}
void expectopen(char **pstr)
{
if (**pstr != '(') throw;
*pstr++;
}
void expectclose(char **pstr)
{
if (**pstr != ')') throw;
*pstr++;
}
void expectchild(char **pstr, int *pdepth)
{
if (**pstr == '0')
{
*pstr++;
return;
}
expectopen(pstr);
expectchild(pstr, &depth);
expectchild(pstr, &depth);
expectclose(pstr);
*pdepth++;
}
A slightly big version. Most of the code is error handling.
#!/usr/bin/env python
import sys
def get_matching_bracket(line, start, count):
if start >= len(line):
return -1
elif line[start] == '(':
return get_matching_bracket(line, start + 1, count + 1)
elif line[start] == ')':
if count == 1:
return start
else:
return get_matching_bracket(line, start + 1, count - 1)
else:
return get_matching_bracket(line, start + 1, count)
def get_one_node(line, start):
if start >= len(line):
return -1, None
if line[start] == '(':
end = get_matching_bracket(line, start, 0)
if end == -1:
return -1, None
return line[start : end + 1], end + 1
elif line[start] == ')':
return -1, None
elif line[start] == '0':
return line[start], start + 1
else:
return -1, -1
def get_left_right(line):
left, rightStart = get_one_node(line, 0)
if rightStart is None:
return -1, -1
right, rightEnd = get_one_node(line, rightStart)
if rightEnd is None:
return -1, -1
if rightEnd <= len(line) - 1:
return -1, -1
return left, right
# ((00)(00))
# (00)
def get_depth(line):
if line[0] == '(':
end = get_matching_bracket(line, 0, 0)
if end == -1:
return -1
left, right = get_left_right(line[1:end])
if -1 in (left, right):
return -1
leftDepth = get_depth(left)
rightDepth = get_depth(right)
if -1 in (leftDepth, rightDepth):
return -1
return 1 + max(get_depth(left), get_depth(right))
else:
return 0
depth = get_depth(sys.argv[1])
if depth != -1:
depth -= 1
print depth
#include <iostream>
#include <string>
using namespace std;
int checkTree(string inp) {
try {
string left,right;
if(inp=="0") return 0;
if(inp=="(00)") return 1;
if(inp[1]=='0') {
left = inp[1];
right = inp.substr(2,inp.length()-3);
}
else {
int index=1,count = 0;
do {
if(inp[index] == '(' ) count ++;
if(inp[index] == ')' ) count --;
index++;
} while(count>0);
left = inp.substr(1,index-1);
right = inp.substr(index,inp.length()-index-1);
}
int lTree = checkTree(left);
int rTree = checkTree(right);
if(lTree==-1 || rTree==-1) return -1;
else return (std::max(lTree,rTree) + 1);
}
catch(...) {
return -1;
}
};
main()
{
cout << "(00): " << checkTree("(00)") << endl;
cout << "((00)0): " << checkTree("((00)0)") << endl;
cout << "((00)(00)): " << checkTree("((00)(00))") << endl;
cout << "((00)(0(00))): " << checkTree("((00)(0(00)))") << endl;
cout << "((00)(0(0(00)))): " << checkTree("((00)(0(0(00))))") << endl;
cout << "x: " << checkTree("x") << endl;
cout << "0: " << checkTree("0") << endl;
cout << "(): " << checkTree("()") << endl;
cout << "(0): " << checkTree("(0)") << endl;
cout << "(00)x: " << checkTree("(00)x") << endl;
cout << "(0p): " << checkTree("(0p)") << endl;
}
int solve(string s){
if (s == "(00)")
return 0;
if (s.size() <= 4 || s[0] != '(' || s[s.size()-1] != ')')
return -1;
int i, n = (int)s.size(), lhs = -1, rhs = -1;
if (s[1] == '0'){ // left node is null
rhs = solve(s.substr(2, n-3));
if (rhs == -1)
return -1;
return rhs + 1;
}
else if (s[n-2] == '0'){ // right node is null
lhs = solve(s.substr(1, n-3));
if (lhs == -1)
return -1;
return lhs + 1;
}
else{
i = 1;
if (s[i] != '(')
return -1;
int cnt[2] = {1, 0};
i++;
for (; i < n-1; i++){
if (s[i] == '(')
cnt[0]++;
else if (s[i] == ')'){
cnt[1]++;
if (cnt[1] == cnt[0])
break;
}
else if (s[i] != '0')
return -1;
}
if (i == n - 1)
return -1;
lhs = solve(s.substr(1, i));
rhs = solve(s.substr(i+1, n-i-2));
if (lhs == -1 || rhs == -1)
return -1;
return max(lhs, rhs) + 1;
}
}
OOps! posting the code again.
public static int findDepth(String str) {
int depth = 0;
String tempStr = str;
while(!tempStr.equals("(00)")) {
if(tempStr.indexOf("(00)") == -1)
return -1;
tempStr = tempStr.replace("(00)", "0");
depth++;
}
return depth;
}
public static int findDepth(String str){
Stack<Integer> stack = new Stack<Integer>();
int maxdep = -1;
stack.push(0);
for(int i = 0; i < str.length(); i ++){
char c = str.charAt(i);
if(stack.isEmpty()) return -1;
Integer oldcount = stack.pop();
switch(c){
case '(':
if(oldcount >= 2) return -1;
stack.push(oldcount+1);
stack.push(0);
break;
case '0':
if(oldcount >= 2) return -1;
stack.push(oldcount+1);
break;
case ')':
if(oldcount != 2) return -1;
if(maxdep < stack.size()-1) maxdep = stack.size()-1;
break;
default:
return -1;
}
}
if(stack.size()!=1 || stack.pop()!= 1) return -1;
else return maxdep;
}
}
/**
* Consider this string representation for binary trees. Each node is of the form (lr),
* where l represents the left child and r represents the right child. If l is the character 0,
* then there is no left child. Similarly, if r is the character 0, then there is no right child.
* Otherwise, the child can be a node of the form (lr), and the representation continues recursively.
For example: (00) is a tree that consists of one node. ((00)0) is a two-node tree in which the root has a left child,
and the left child is a leaf. And ((00)(00)) is a three-node tree, with a root, a left and a right child.
*/
/**
* Solution:
*
* The idea is to verify the following three cases:
*
* (0 , (..))
* ((...) , 0)
* ((...) (...))
*
* At each recursive step we identify which possible case (the ones listed above) are we at and we verify if the string is correct.
* As we traverse the subtrees, at each recursive step we check if the "inner" brackets forming the subtrees are valid or not. This
* applied recursively checks that every string representing a subtree is well formed.
*/
public class SerializedTreeDepth {
public static void main(String [] args) {
String tree ="((00)((00)(00)))" ;
calculateDepth(tree);
tree = "(0(00))";
calculateDepth(tree);
tree = "()()";
calculateDepth(tree);
tree = "((1234)(5678))";
calculateDepth(tree);
tree = "(00)" ;
calculateDepth(tree);
}
private static int calculateDepth(String tree) {
int begin = 0 ;
int end = tree.length() - 1;
int depth = findDepth(begin , end , tree , 0);
System.out.println("Depth: " + depth);
return depth;
}
public static int findDepth(int begin, int end, String tree , int depth) {
//System.out.println("Substring: " + tree.substring(begin, end+1) + " depth:" + depth);
boolean leftSubTreeNull = false ;
boolean rightSubTreeNull = false;
int leftSubTreeBegin ;
int leftSubTreeEnd ;
int rightSubTreeBegin ;
int rightSubTreeEnd ;
int depthLeft = 0 ;
int depthRight = 0 ;
// We have a valid subtree so far
if(tree.charAt(begin) != '(' ||
tree.charAt(end) != ')' ) {
return -1;
}
// Is the left subtree null ?
if(tree.charAt(begin + 1) == '0') {
leftSubTreeNull = true;
}
// Is the right subtree null ?
if(tree.charAt(end - 1) == '0') {
rightSubTreeNull = true;
}
// If this is a leaf node ; then the length of the current subtree string must be 3 ; otherwise this string is invalid
if(leftSubTreeNull && rightSubTreeNull) {
if(end - begin == 3) {
return depth ;
} else {
return -1 ;
}
}
// Case 1: If the left subtree is null and the right subtree is not null
// Example: (0( ...))
if(leftSubTreeNull && !rightSubTreeNull) {
if(tree.charAt(begin + 2) != '(') {
return -1 ;
}
if(tree.charAt(end -1) != ')') {
return -1 ;
}
rightSubTreeBegin = begin + 2 ;
rightSubTreeEnd = end -1 ;
if(verifyBrackets(tree , rightSubTreeBegin, rightSubTreeEnd)) {
depthRight = findDepth(rightSubTreeBegin , rightSubTreeEnd , tree , depth+1);
return depthRight;
} else {
return -1 ;
}
}
// Case 2: Same logic as above but vice versa
// Example: ((...) 0)
if(rightSubTreeNull && !leftSubTreeNull) {
if(tree.charAt(begin + 1) != '(') {
return -1 ;
}
if(tree.charAt(end - 2) != ')') {
return -1 ;
}
leftSubTreeBegin = begin + 1 ;
leftSubTreeEnd = end - 2 ;
if(verifyBrackets(tree, leftSubTreeBegin , leftSubTreeEnd)) {
depthLeft = findDepth(leftSubTreeBegin , leftSubTreeEnd , tree , depth+1);
return depthLeft;
} else {
return -1 ;
}
}
// Case 3: The structure should look like:
// ((...) (...))
if(!leftSubTreeNull && !rightSubTreeNull) {
if(tree.charAt(begin + 1) != '(') {
return -1 ;
}
if(tree.charAt(end -1) != ')'){
return -1 ;
}
int j = begin + 1 ;
int k = end - 1 ;
int bracketsRight = 0 ;
int bracketsLeft = 0;
leftSubTreeBegin = begin + 1 ;
rightSubTreeEnd = end -1 ;
while(j < tree.length()) {
if(tree.charAt(j) == '(') {
bracketsLeft++;
} else if (tree.charAt(j) == ')') {
bracketsLeft--;
}
if(bracketsLeft == 0) {
break;
}
j++;
}
// If the brackets are not valid or the right subtree is missing ; the string is invalid
if(bracketsLeft != 0 || j == tree.length()) return -1 ;
leftSubTreeEnd = j ;
while (k >= 0) {
if(tree.charAt(k) == '(') {
bracketsRight--;
} else if (tree.charAt(k) == ')') {
bracketsRight++;
}
if(bracketsRight == 0) {
break;
}
k--;
}
rightSubTreeBegin = k ;
if (bracketsRight != 0 || rightSubTreeBegin != leftSubTreeEnd + 1) return -1 ;
depthLeft = findDepth(leftSubTreeBegin , leftSubTreeEnd , tree , depth+1);
depthRight = findDepth(rightSubTreeBegin , rightSubTreeEnd , tree , depth+1);
}
if(depthLeft > depthRight) return depthLeft; else return depthRight;
}
private static boolean verifyBrackets(String tree, int begin, int end) {
int brackets = 0;
for(int i = begin ; i <= end ; i++) {
if(tree.charAt(i) == '(' ) {
brackets ++;
} else if (tree.charAt(i) == ')') {
brackets--;
}
}
return brackets == 0 ;
}
}
Use Stack and it's very easy.
1) Your stach contains '(' at the start
2) Now scan 1 char at a time in given string
2a) if char is '(' , push 2 '(' on stack
2b) if char is '0' or ')' then pop one char from stack. is stack is empty then return -1;
3) At the end your stack must be empty.
public static int cntNodes(String str) {
int cnt = 0;
Stack <Character> st = new Stack <Character>();
st.push('(');
int n = str.length();
for(int i = 0; i < n; i++) {
char ch = str.charAt(i);
switch(ch) {
case '(':
cnt++;
st.push('(');
st.push('(');
break;
case ')':
case '0':
if(st.size() == 0) {
return -1;
}
st.pop();
break;
default:
return -1;
}
}
if(st.size() == 0) {
return cnt;
} else {
return -1;
}
}
Working C code. Seems to pass the test cases which have been discussed.
void findDepth(char * str){
int i=0,depth =0,counter =0;
int len = strlen(str);
if(len < 4){
printf("\n Malformed String \n");
}
else{
for(i=0;i<len;i++){
if(str[i] == '('){
depth++;
if(str[i+1]=='0' && str[i+2]=='0');
if(str[i+1]=='0' && str[i+2]==')'){
printf("\n Malformed String \n");
break;
}
if(str[i+1]== '0' && str[i+2]=='(')
counter++;
}
else if(str[i] == ')' && depth == 0){
printf("\n Malformed String \n");
break;
}
else if( str[i] == ')' && depth > 0){
depth --;
}
else if(str[i]!='0' || str[i] !='(' || str[i] != ')'){
// printf("\n Malformed String");
break;
}
}
if(depth == 0)
printf("\n The depth of the given tree is %d", counter == 0? counter:counter +1);
else
printf("\n Malformed String");
}
}
#include <stdio.h>
using namespace std;
//edge case: ()
//edge case: 0)
//edge case: (00)
//edge case: (0(0(00)))
//edge case: ((00)(00))
//edge case: ((00)(((00)(00))0))
//edge case: (0)
//edge caes: (0p)
//edge case: (000)
//edge case: (0(00)
//edge case: )(00)
#define N 100
int find_depth_2(const char* str)
{
int depth = 0;
int top = -1;
char stack[N + 1] = {0};
int max_depth = -1;
const char* p;
for (p = str; *p; p++)
{
if (*p == ')')
{
if (top > 1 && stack[top] == '0' && stack[top - 1] == '0' && stack[top - 2] == '(')
{
top-=3;
stack[++top] = '0';
max_depth = (max_depth < depth ? depth : max_depth);
depth--;
}
else
{
return -1;
}
}
else
{
stack[++top] = *p;
if (*p == '(')
{
depth++;
}
}
}
if (top == 0 && stack[top] == '0')
{
return max_depth;
}
return -1;
}
int find_depth(const char* str)
{
int depth = 0;
int max_depth = -1;
int stack[N + 1] = {0};
int top = 0;
const char* p;
for (p = str; *p ; p++)
{
if (*p == '(')
{
if (stack[top] == 1)
{
stack[++top] = 2;
stack[++top] = 1;
}
else if(stack[top] == 2)
{
stack[++top] = 3;
stack[++top] = 1;
}
else if (stack[top] == 0)
{
stack[++top] = 1;
}
else
{
return -1;
}
depth++;
}
else if (*p == ')')
{
if (stack[top] == 3)
{
top--;
if (stack[top] == 2)
{
top--;
if (stack[top] == 1)
{
top--;
max_depth = (max_depth < depth ? depth : max_depth);
depth--;
continue;
}
}
return -1;
}
else
{
return -1;
}
}
else if (*p == '0')
{
if (stack[top] == 1)
{
stack[++top] = 2;
}
else if (stack[top] == 2)
{
stack[++top] = 3;
}
else
{
return -1;
}
}
else
{
return -1;
}
}
if (*p == 0 && top == 0 && stack[top] == 0)
{
return max_depth;
}
return -1;
}
int main() {
const char* test = ")(00)";
printf("%d\n", find_depth(test));
printf("%d\n", find_depth_2(test));
return 0;
}
in Java you can write:
int parseTree(String s) {
if (s.length() < 4)
return -1;
Stack<Character> stack = new Stack<Character>();
int maxLevel = -1, level = -1;
try {
int i=0;
while ( i < s.length() ) {
if (s.charAt(i) == '(') {
stack.push('(');
++level;
if (level > maxLevel)
maxLevel = level;
}
else if (s.charAt(i) == '0') {
stack.push('0');
}
else if (s.charAt(i) == ')') {
if (stack.peek() != '0') return -1;
stack.pop();
if (stack.peek() != '0') return -1;
stack.pop();
if (stack.peek() != '(') return -1;
stack.pop();
stack.push('0');
--level;
}
else {
return -1;
}
++i;
}
if (stack.size() == 1 && stack.peek() == '0') {
return maxLevel;
}
}
catch (Exception e) {
}
return -1;
}
I have a O(dn) solution where d is the depth of the tree and n is the length of the string.
int find_depth(string str) {
int count = -1;
bool found;
if (str.length() < 4)
return -1;
while (str != "0") {
cout << str << endl;
found = false;
int len = str.length();
int i = 0;
while (i<len){
if (str[i] == ')') {
if (i >= 3 && str.substr(i-3,4)=="(00)") {
string temp = str.substr(0, i - 3) + "0" + str.substr(i + 1, len - i - 1);
len = len - 3;
str = temp;
found = true;
}
else
return -1;
}
i++;
}
if (found == false)
return -1;
else
count++;
}
return count;
}
A Simple Solution which runs in O(n) and O(n) extra space (Stack space)
exception e;
void popStack(stack<char>& stk, char popChar) {
if (stk.empty() || stk.top() != popChar)
throw e;
stk.pop();
}
int find_depth(string str) {
stack<char> stk;
int depth = -1;
int currentLevel = -1;
int length = str.length();
char currentChar;
if (length<4)
return -1;
int i;
for (i=0; i<length; i++) {
currentChar = str[i];
if (currentChar == '(' || currentChar == '0') {
stk.push(currentChar);
if (currentChar == '(')
currentLevel++;
if (depth < currentLevel)
depth = currentLevel;
}
else if (currentChar == ')') {
try {
popStack(stk, '0');
popStack(stk, '0');
popStack(stk, '(');
currentLevel--;
}
catch (exception &e) {
return -1;
}
if (stk.empty())
break;
stk.push('0');
}
else
return -1;
}
if (i != length - 1)
return -1;
return depth;
}
int getDepth(string s)
{
int depth = 0;
int depthMax = 0;
vector<char> v;//convert (00) to 0
if(s.back() != ')')
return -1;
for(int i=0;i<s.length();i++)
{
if(s[i] == '(')
{
depth++;
if(depth > depthMax)
depthMax = depth;
v.push_back('(');
}
else if(s[i] == '0')
{
v.push_back('0');
}
else if(s[i] == ')')
{
depth--;
if(v.empty() || v.back() != '0')
return -1;
v.pop_back();
if(v.empty() || v.back() != '0')
return -1;
v.pop_back();
if(v.empty() || v.back() != '(')
return -1;
v.pop_back();
v.push_back('0');
}
else
return -1;
}
if(v.back() != '0' || v.size() != 1)
return -1;
return depthMax-1;
}
#include <iostream>
#include <string>
#include <stack>
#include <limits.h>
using namespace std;
bool validate(string s) {
string& last = s;
while(last.find("(00)") != string::npos) {
int i = 0;
int n = last.size();
string temp="";
while(i < n) {
if (string(last, i, 4) == "(00)") {
i += 4;
temp += "0";
} else {
temp.append(1,last[i]);
i++;
}
}
last = temp;
}
return (last == "0" ? true : false);
}
int getDepth(string s) {
if (validate(s) == false) {
return -1;
}
int n = s.size();
stack<char> st;
int depth = INT_MIN;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
st.push(s[i]);
} else if (s[i] == ')') {
st.pop();
}
depth = max(depth, (int)st.size());
}
return depth;
}
int main() {
cout << getDepth("(00)") << "\n";
cout << getDepth("(00)0") << "\n";
cout << getDepth("((00)0)") << "\n";
cout << getDepth("((00)00)") << "\n";
cout << getDepth("((00)(00))") << "\n";
cout << getDepth("((00)0(00))") << "\n";
cout << getDepth("((00)(0o))") << "\n";
cout << getDepth("()") << "\n";
cout << getDepth("(0)") << "\n";
cout << getDepth("((0((00)0))(00))") << "\n";
}
public static int getHeight(String expression) {
if (expression == null || expression.isEmpty()) {
return 0;
}
if (expression.length() < 4) {
return -1;
}
int height = 0;
while(expression.contains("(00)")) {
expression = expression.replaceAll("\\(00\\)", "0");
height++;
}
if (expression.equals("0")) {
return height;
} else {
return -1;
}
}
This is a parsing program. We have a grammar like:
P = '(' Q Q ')'
Q = 0 | P
So the following top-down recursion based parsing should work. The complexity is N.
int P(string &input, int &curr) {
if (input.size() >= input.size()) {
return -1;
}
if (str.at(curr++) != '(') {
return -1;
}
int d1 = Q(input, curr);
if (d1 < 0) {
return -1;
}
int d2 = Q(input, curr);
if (d2 < 0) {
return -1;
}
if (curr >= input.size()) {
return -1;
}
if (input.at(curr++) != ')') {
return -1;
}
return 1 + max (d1, d2);
}
int Q(string &input, int &curr) {
if (curr >= input.size()) {
return -1;
}
switch (input.at(curr++)) {
case '0': return 0;
case '(': return P(input, curr);
default: return -1;
}
}
int parse(string &input) {
int curr = 0;
return P(input, curr);
}
It can be done in two phases:
Step 1: Find if the string represents valid binary tree
Step 2: If valid tree, find depth
Step 1 Approach: Replace all (00) occurances with 0, At end, if you end up with a 0, then it is valid binary tree, else not. We can use simple stack to do this,
As we go from left to right in the string,
if element == '(' or '0', push element
if element == ')', then pop last three elements, check if the order of popped elements is
0, 0, ( and if yes, push 0
else return -1 (means not valid binary tree)
At end, check if the stack has only element 0, then return 1 (means valid binary tree), else return -1.
This is O(N)
Step 2 logic: - done only if step 1 return true or valid binary tree
Again go from left to right in string, and incement count when '(' and decrement when ')'.
When incrementing, always check if count is greater than max, and if yes, update max to new count.
After going thru all elements, the value of max -1 is depth. (max minus 1 needed since depth starts numbering from 0)
Actually, we needn't compare the occurrence of ( or ), we just need to replace "(00)" with "0" and recur the process, return the times of replacement. See my code below:
- Daisy April 18, 2012<?php $input = ')0('; getDepth($input); function getDepth($input) { $replace = '0'; $pattern = '/\(00\)/'; $count = 0; $str = $input; $time = -1; // echo $input . "<br />"; do { $time = $time + 1; $str = preg_replace($pattern, $replace, $str, -1, $count); // echo "<br /> count:"; // echo $count; // echo "<br />"; } while ($count != 0); if ($time != 0 && $str == '0' && $input != '0') { $res = $time - 1; } else { $res = - 1; } // echo "result:$res"; return $res; } ?>