Author |
Topic: Finding depth of a binary tree (Read 13869 times) |
|
mcprabhakaran
Junior Member
Posts: 62
|
 |
Finding depth of a binary tree
« on: May 16th, 2007, 4:33am » |
 Quote  Modify
|
Hi Friends,
How to find the depth of a binary tree. I hope that I am having an inefficient algorithm. I wish to know the best algorithm. 
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Finding depth of a binary tree
« Reply #1 on: May 16th, 2007, 5:07am » |
Quote Modify
|
Traverse the tree. Remember the max length.
If you need it often, maintain the number of children for each node. It's at the expense of slower updates.
|
|
IP Logged |
|
|
|
Fighter
Newbie
Posts: 8
|
|
Re: Finding depth of a binary tree
« Reply #2 on: May 23rd, 2007, 5:30am » |
Quote Modify
|
int depth(Root T)
{
if(T == NULL)
return 0;
d1 = depth(T -> left);
d2 = depth(T -> right);
return (max(d1,d2) + 1);
}
|
|
IP Logged |
|
|
|
mcprabhakaran
Junior Member
Posts: 62
|
|
Re: Finding depth of a binary tree
« Reply #3 on: May 26th, 2007, 10:17pm » |
Quote Modify
|
Fine.
Here is another one small problem...
How to count no.of nodes in each level..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding depth of a binary tree
« Reply #4 on: May 27th, 2007, 8:36am » |
Quote Modify
|
A breadth first search would work. Two stack (or queues) would probably work best, otherwise you need something else to keep track of which level you in. (With two stacks, you switch level when you switch stacks; i.e. when one is empty).
Just count one stack, put the children of nodes there on the other; switch, repeat. etc
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Nemo
Newbie
Posts: 1
|
|
Re: Finding depth of a binary tree
« Reply #5 on: May 29th, 2007, 12:49am » |
Quote Modify
|
on May 27th, 2007, 8:36am, towr wrote: Two stack (or queues) would probably work best, otherwise you need something else to keep track of which level you in. (With two stacks, you switch level when you switch stacks; i.e. when one is empty).
Just count one stack, put the children of nodes there on the other; switch, repeat. etc |
|
Hey Towr, Can you please specify exactly how the procedure wud work ?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding depth of a binary tree
« Reply #6 on: May 29th, 2007, 3:30am » |
Quote Modify
|
something like:
level = 0
thisLevel = empty stack
push root on thisLevel
while( thisLevel is not empty )
{
print "the count for level " level " is " thisLevel.size()
nextLevel = empty stack
while( thisLevel is not empty ){
pop node from thisLevel
push node.left on nextLevel if not null
push node.right on nextLevel if not null
}
level = level+1
thisLevel = nextLevel;
}
But you could swap the stacks instead of creating and destroying empty stacks.
|
|
IP Logged |
|
|
|
Sriram
Newbie
Gender:
Posts: 15
|
|
Re: Finding depth of a binary tree
« Reply #7 on: May 29th, 2007, 8:40am » |
Quote Modify
|
What about having an array A such that A[L] gives the total number of nodes at Level L. Something like
Code:int A[MAX_LEVELS];
void DFS(Node* root, int curlevel)
{
if(root == NULL) return;
A[curlevel] = A[curlevel] + 1;
DFS(root->left, curlevel+1);
DFS(root->right, curlevel+1);
} |
|
|
| « Last Edit: May 29th, 2007, 8:41am by Sriram » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding depth of a binary tree
« Reply #8 on: May 29th, 2007, 8:46am » |
Quote Modify
|
It is probably faster. You could even use some dynamic array to avoid setting a max length.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding depth of a binary tree
« Reply #9 on: May 29th, 2007, 8:54am » |
Quote Modify
|
You could use a list instead of an array. With a dynamic array you would have to resize it, I think.
On the other hand, the multiple indirection in going through a list isn't too good in itself. Doubling a dynamic array each time it proves too small should limit the extra work and may end up being better overall.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding depth of a binary tree
« Reply #10 on: May 29th, 2007, 9:04am » |
Quote Modify
|
I just thought of a funny use of a stack 
void countLevels(root)
{
stack = empty stack
fillStack(root)
level = 0
while( stack is not empty ){
print "level " + level + ": " + stack.pop();
}
}
void fillStack(root){
if( root==null ) return;
if( stack is empty ){
count = 0
} else {
count = stack.pop();
}
fillStack(root.left);
fillStack(root.right);
stack.push(count+1);
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding depth of a binary tree
« Reply #11 on: Dec 21st, 2007, 7:37am » |
Quote Modify
|
on Dec 21st, 2007, 5:55am, gokul wrote: I have a question related to traversal in a binary tree.
How can i make a breadth first traversal? ie display the node elements level by level. |
|
Why ask again, when I already answered it when you asked here?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Finding depth of a binary tree
« Reply #12 on: Dec 21st, 2007, 4:34pm » |
Quote Modify
|
And if you need to know number of nodes at each level often, you can speed up this query by maintaining result for each subtree. For ballanced trees the query will take O(log n) time, but each update will slowdown from O(log n) to O(log^2 n).
(Adding leaf results in O(log n) statistic updates, but a rotation can introduce a lot of updates on higher level.) There is also the O(log n) space required per node...
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Finding depth of a binary tree
« Reply #13 on: Mar 8th, 2008, 3:00am » |
Quote Modify
|
Another Question-
There is a binary tree total nodes are n (1...n), and you are given an array A[1...n]
such that A contain parent of node i, and A[root] contian -1. You have to find the
depth of the tree.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding depth of a binary tree
« Reply #14 on: Mar 8th, 2008, 6:09am » |
Quote Modify
|
on Mar 8th, 2008, 3:00am, mad wrote:Another Question-
There is a binary tree total nodes are n (1...n), and you are given an array A[1...n]
such that A contain parent of node i, and A[root] contian -1. You have to find the
depth of the tree. |
|
Make an array B, initiallized with, say, -1. Set B[-1]=0. Then for each i in A, if B[i] != -1, move on, otherwise if B[A[i]] != -1 then B[i] = B[A[i]]+1; else recurse to i'=A[i] to find it's depth before continuing.
In the end B contains the depths of all nodes, so pick the maximum.
|
| « Last Edit: Mar 8th, 2008, 6:09am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Finding depth of a binary tree
« Reply #15 on: Mar 8th, 2008, 1:54pm » |
Quote Modify
|
on May 16th, 2007, 4:33am, mcprabhakaran wrote:Hi Friends,
How to find the depth of a binary tree. I hope that I am having an inefficient algorithm. I wish to know the best algorithm. |
|
traverse level order(known as breadth first traversal) on a binary tree. The last level is the depth.
|
|
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Finding depth of a binary tree
« Reply #16 on: Mar 8th, 2008, 2:00pm » |
Quote Modify
|
on May 26th, 2007, 10:17pm, mcprabhakaran wrote:Fine.
Here is another one small problem...
How to count no.of nodes in each level.. |
|
use level order traversal...with very little modification of putting an end marker after each level...so whenever u get this endmarker...u know the end of level...
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Finding depth of a binary tree
« Reply #17 on: Mar 9th, 2008, 9:41pm » |
Quote Modify
|
on Mar 8th, 2008, 6:09am, towr wrote:
Make an array B, initiallized with, say, -1. Set B[-1]=0. Then for each i in A, if B[i] != -1, move on, otherwise if B[A[i]] != -1 then B[i] = B[A[i]]+1; else recurse to i'=A[i] to find it's depth before continuing.
In the end B contains the depths of all nodes, so pick the maximum.
|
|
This method is O(n log n). Can it be solved in O(n)?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding depth of a binary tree
« Reply #18 on: Mar 10th, 2008, 1:44am » |
Quote Modify
|
on Mar 9th, 2008, 9:41pm, mad wrote:| This method is O(n log n). Can it be solved in O(n)? |
|
It is O(n)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Finding depth of a binary tree
« Reply #19 on: Mar 10th, 2008, 1:56am » |
Quote Modify
|
on Mar 9th, 2008, 9:41pm, mad wrote:
This method is O(n log n). Can it be solved in O(n)? |
|
It is O(n) since the algorithm traverses each edge atmost twice. This algorithm we can apply for general trees also.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print