recursion and binary trees

This is a discussion on recursion and binary trees within the C++ Programming forums, part of the General Programming Boards category; Hey guys, i was wondering if anyone could explain this to me Code: int maxdepth (treeptr tree){ int leftdepth = ...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    36

    recursion and binary trees

    Hey guys, i was wondering if anyone could explain this to me
    Code:
    	int maxdepth (treeptr tree){
    		int leftdepth = 0;
    		int rightdepth = 0;
    
    		if (tree == NULL)
    			return 0;
    		else{
    			leftdepth = maxdepth(tree->left);
    			rightdepth = maxdepth(tree->right);
    			if (leftdepth > rightdepth)
    				return leftdepth +1;
    			else 
    				return rightdepth + 1;
    		}
    	}
    This is supposed to calculate the maximun 'depth' of the binary tree. However, I don't see the part in which left/right depth is ever incremented. Infact, is it not just reset to 0 all the time?

    Also, in the code for traversing a tree
    Code:
    void traverse(treeptr tree){
    		traverse(tree->left);
                    cout  << tree->data;
    		traverse(tree->right);
    	}
    How does the function ever break its recursion loop? Surely it would just keep going on and on.

    many thanks,

  2. #2
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    Just a quick note, i think i understand the last bit
    Code:
    if (leftdepth > rightdepth)
    				return leftdepth +1;
    			else 
    				return rightdepth + 1;
    Basically, if the the tree is greater on the left side then return that number + 1, (+1 due to the 'root' or 'head' of the binary tree being included) am i right in thinking this?

    I still am unsure how the value leftdepth,right depth is calculated.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The traverse function you posted is indeed broken in the way you describe.

    leftdepth is calculated right there where it's assigned:
    Code:
    leftdepth = maxdepth(tree->left);
    I'll give you the same advice I gave earlier: draw a silly little tree (two nodes, maybe) and trace through the algorithm. You'll see how it works.

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    you know, i think you're right. I think it did help. But when the does the tree == NULL?
    is there a 'NULL' node at the end of each branch?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by rocketman50 View Post
    you know, i think you're right. I think it did help. But when the does the tree == NULL?
    is there a 'NULL' node at the end of each branch?
    If you've built the tree in any kind of normal way, yes.

  6. #6
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    cool, thanks for the help.

    Just to clarify - im being slow (its 4am ><)

    The base case is tree == NULL.
    So the function will start by traversing down the left most branch until it reaches the base case. From there, it will sort of work backwards to find the maxdepth of the leftside. It will then repeat for the right side, compare which is larger and return that side.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by rocketman50 View Post
    cool, thanks for the help.

    Just to clarify - im being slow (its 4am ><)

    The base case is tree == NULL.
    So the function will start by traversing down the left most branch until it reaches the base case. From there, it will sort of work backwards to find the maxdepth of the leftside. It will then repeat for the right side, compare which is larger and return that side.
    Well, that side plus one, but yes.

  8. #8
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    great, I really appreciate the help. I have an exam tomorrow. I should really be asleep right about now...i really need to get my head around recursion first!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  2. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. recursion in binary trees problem newbie
    By totalfreeloader in forum C++ Programming
    Replies: 2
    Last Post: 05-13-2003, 06:17 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21