A Bhattacharya

Ranch Hand

Posts: 125

posted 9 years ago

I gave the following answer in the telephone interview:

boolean isBalanced(Tree *t,int *height)

{

if(t==NULL)

{

*height = 0;

return true;

}

int leftheight,rightheight;

boolean leftBalanced = isBalanced(t->lptr,&leftheight)

boolean rightBalanced = isBalanced(t->rptr,&rightheight)

bolean balanced = leftBalanced && rightBalanced && abs(leftheight-rightheight)<=1

*height = 1+max(leftheight,rightheight)

return balanced

}

I didn't dictate line by line but explained the above logic in words. I said the time complexity is O(n) where n is the no of nodes in the tree. But he insisted like idiot that the complexity is O(n^2) and was saying that for each subtree we will have to process all the nodes in the subtree but I kept saying that we process each node exactly once. I think he either didn't understand my answer properly or was stuck up with an inefficient algorithm he had in mind. My question is, is my algorithm correct or not?

boolean isBalanced(Tree *t,int *height)

{

if(t==NULL)

{

*height = 0;

return true;

}

int leftheight,rightheight;

boolean leftBalanced = isBalanced(t->lptr,&leftheight)

boolean rightBalanced = isBalanced(t->rptr,&rightheight)

bolean balanced = leftBalanced && rightBalanced && abs(leftheight-rightheight)<=1

*height = 1+max(leftheight,rightheight)

return balanced

}

I didn't dictate line by line but explained the above logic in words. I said the time complexity is O(n) where n is the no of nodes in the tree. But he insisted like idiot that the complexity is O(n^2) and was saying that for each subtree we will have to process all the nodes in the subtree but I kept saying that we process each node exactly once. I think he either didn't understand my answer properly or was stuck up with an inefficient algorithm he had in mind. My question is, is my algorithm correct or not?

Campbell Ritchie

Marshal

Posts: 55681

161

posted 9 years ago

You only inspect each node once, you yes, it is O(n). The reason the other guy may be confused is the order of inspecting - that's not linear.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Brian Cole

Author

Ranch Hand

Ranch Hand

Posts: 949

1

posted 9 years ago

First, the algorithm is definitely linear in the number of nodes. Not sure what he was thinking to claim O(n^2).

Second, I'm not sure it's correct, depending on what exactly we mean by "fully balanced." Consider the tree

[edit: See below for a fantasmic ASCII-graphic pictoral representation. Also, I may be quoting depth values one lower than your algorithm's, but I believe my meaning is clear.]

[ May 08, 2008: Message edited by: Brian Cole ]

Originally posted by A Bhattacharya:

I gave the following answer in the telephone interview:

boolean isBalanced(Tree *t,int *height)

{

if(t==NULL)

{

*height = 0;

return true;

}

int leftheight,rightheight;

boolean leftBalanced = isBalanced(t->lptr,&leftheight)

boolean rightBalanced = isBalanced(t->rptr,&rightheight)

bolean balanced = leftBalanced && rightBalanced && abs(leftheight-rightheight)<=1

*height = 1+max(leftheight,rightheight)

return balanced

}

I didn't dictate line by line but explained the above logic in words. I said the time complexity is O(n) where n is the no of nodes in the tree. But he insisted like idiot that the complexity is O(n^2) and was saying that for each subtree we will have to process all the nodes in the subtree but I kept saying that we process each node exactly once. I think he either didn't understand my answer properly or was stuck up with an inefficient algorithm he had in mind. My question is, is my algorithm correct or not?

First, the algorithm is definitely linear in the number of nodes. Not sure what he was thinking to claim O(n^2).

Second, I'm not sure it's correct, depending on what exactly we mean by "fully balanced." Consider the tree

**((a(bc))((de)((fg)h)))**. The left subtree

**(a(bc))**is balanced with depth 2. The right subtree

**((de)((fg)h))**is balanced with depth 3. However leaf

**a**has depth 2 while leaf

**f**has depth 4.

[edit: See below for a fantasmic ASCII-graphic pictoral representation. Also, I may be quoting depth values one lower than your algorithm's, but I believe my meaning is clear.]

[ May 08, 2008: Message edited by: Brian Cole ]

A Bhattacharya

Ranch Hand

Posts: 125

Brian Cole

Author

Ranch Hand

Ranch Hand

Posts: 949

1

A Bhattacharya

Ranch Hand

Posts: 125

posted 9 years ago

Thanks for the picture. It is ok for 'a' to be at depth 2 and 'f' at depth 4. If you are comparing the heights of left and right subtrees of the root node, you should not even consider 'a' because it is not the deepest node in the left subtree.

Brian Cole

Author

Ranch Hand

Ranch Hand

Posts: 949

1

posted 9 years ago

You're welcome.

That's why I said "depending on what exactly we mean by 'fully balanced.'"

In fact, some people define "fully balanced" to mean every leaf has exactly the same depth, which is pretty restrictive in that no binary tree with a leaf-count that is not a power of two can qualify. Note that the tree I demonstrated can be rebalanced to meet this definition:

If it were up to me, I'd say a "fully balanced" tree is one where the depths of any two leaves differ by at most one. I'd say the tree I demonstrated, where the depths of

[ May 08, 2008: Message edited by: Brian Cole ]

Originally posted by A Bhattacharya:

Thanks for the picture. It is ok for 'a' to be at depth 2 and 'f' at depth 4. If you are comparing the heights of left and right subtrees of the root node, you should not even consider 'a' because it is not the deepest node in the left subtree.

You're welcome.

That's why I said "depending on what exactly we mean by 'fully balanced.'"

In fact, some people define "fully balanced" to mean every leaf has exactly the same depth, which is pretty restrictive in that no binary tree with a leaf-count that is not a power of two can qualify. Note that the tree I demonstrated can be rebalanced to meet this definition:

**(((ab)(cd))((ef)(gh)))**

If it were up to me, I'd say a "fully balanced" tree is one where the depths of any two leaves differ by at most one. I'd say the tree I demonstrated, where the depths of

**a**and

**f**differ by two, could possibly be considered "balanced" but not "fully balanced." But that's just me--feel free to use your own definition. (During a job interview, it might be wise to agree on a definition.)

[ May 08, 2008: Message edited by: Brian Cole ]