depth of binary tree

This is a discussion on depth of binary tree within the C Programming forums, part of the General Programming Boards category; Code: int depth(cvor *root) { int left, right; if(root) { left = depth(root->left); right = depth(root->right); return 1 + (left ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272

    depth of binary tree

    Code:
    int depth(cvor *root)
    {
        int left, right;
        
        if(root) {
            left = depth(root->left);
            right = depth(root->right);
            return 1 + (left > right ? left : right);
        }
        return 0;
    }
    Can anyone help me understand this function?

    I tried writing it down on paper but i just cant visualize how this works....

    Should i try finding an animation of this on the internet and learning it like that? Or just write all calls to paper and try to understand how it works...

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Since it's recursive, it may very well help you to draw out a tree on paper, and start at the bottom (since that way you won't have to build a freakishly large recursive thing). You'll see how it works pretty quickly that way, I reckon.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    Looks like it always crawls down whichever is the larger of the two branches at any particular node. I'm not convinced it necessarily finds the longest path that way.

    Plus if the left and right elements are node indexes or pointers (because that's what the recursive call depends on) I don't see a correlation between node pointer and geometrical depth.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by nonoob View Post
    Looks like it always crawls down whichever is the larger of the two branches at any particular node. I'm not convinced it necessarily finds the longest path that way.
    I'm pretty sure it goes down both, what with there being two recursive calls. It passes the larger one up the chain, yes.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,160
    The height of a tree is equal to 1 plus the height of the left subtree or right subtree, whichever is greater. The height of an empty tree is zero.

    If you can understand that, then great. That's exactly what the code says.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. 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
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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