Add to Favorites    Make Home Page 290 Online  

 Language Categories  
 Our Services  

Java Data Structures - Contents


Determining Tree Depth...

A D V E R T I S E M E N T

Search Projects & Source Codes:

    Tree related algorithms depend on tree depth being small (otherwise, they become linked list algorithms ;-). Determining what is the depth of a tree can sometimes lead to optimizations, and other interesting things like that. How then, do you determine tree depth?

    The task seems rather simple, however, there are a few tricks involved. Since most trees are defined recursively, our algorithm will also be recursive. We will need a wrapper method to initialize the maximum depth to zero, and then, recursively go through the tree determining the depth at each node. We will use a counter to keep the count of the current depth. Whenever we enter a recursive method, we will increment the counter, whenever we leave, we will decrement it. If that counter is greater than the maximum tree depth encountered so far, we will set the maximum tree depth to the value of that counter.

    Once the algorithm completes, the variable holding the maximum tree depth will hold the max tree depth (sounds logical doesn't it?) Anyway, talk is cheap, lets go write it!

import java.lang.*;
import java.io.*;

public class pBinTreeDepth{
    public pBinTreeDepth left,right;
    public Integer data;
    private static int tree_depth,curr_depth = 0;
    public static int[] numbers = {7,3,11,2,5,9,12,4,6,8,10};

    public static pBinTreeDepth add(pBinTreeDepth r,Integer n){
        if(r == null){
            r = new pBinTreeDepth();
            r.left = r.right = null;
            r.data = n;
        }else if(r.data.compareTo(n) < 0)
            r.right = add(r.right,n);
        else
            r.left = add(r.left,n);
        return r;
    }

    public static void print(pBinTreeDepth r){
        if(r != null){
            print(r.left);
            System.out.print(" "+r.data);
            print(r.right);
        }
    }

    public static void _getdepth(pBinTreeDepth r){
        if(r != null){
            curr_depth++;
            if(curr_depth > tree_depth)
                tree_depth = curr_depth;
            _getdepth(r.left);
            _getdepth(r.right);
            curr_depth--;
        }
    }

    public static int getdepth(pBinTreeDepth r){
        tree_depth = 0;
        _getdepth(r);
        return tree_depth;
    }

    public static void main(String[] args){
        pBinTreeDepth tree = null;
        System.out.print("inserting: ");
        for(int i=0;i<numbers.length;i++){
            Integer n = new Integer(numbers[i]);
            System.out.print(" "+n);
            tree = add(tree,n);
        }
        System.out.print("\ntree: ");
        print(tree);
        System.out.println("\ndepth: "+getdepth(tree));
        System.out.println("done ;-)");
    }
}

    The code above creates a binary search tree, and then calls the getdepth(pBinTreeDepth) method to get the tree's depth. This method in turn calls _getdepth(pBinTreeDepth), which is the actual recursive procedure. The whole thing is implemented as static methods; this is just to make quick & simple implementation easier.


Back to Table of Contents


A D V E R T I S E M E N T




Google Groups Subscribe to SourceCodesWorld - Techies Talk
Email:


Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

 Advertisements  

Google Search

Google

Source Codes World.com is a part of Vyom Network.

Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Interview Questions | Jobs, Discussions | Placement Papers | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | Arabic, French, German | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Software Testing | Google Logo Maker | Freshers Jobs

Sitemap | Privacy Policy | Terms and Conditions
Copyright ©2003-2014 SourceCodesWorld.com, All Rights Reserved.
Page URL: http://www.sourcecodesworld.com/articles/java/java-data-structures/Determining_Tree_Depth.asp


Download Yahoo Messenger | Placement Papers | Free SMS | C Interview Questions | C++ Interview Questions | Quick2Host Review