Sunday 5 June 2016

Find the Maximum Depth or Height of a Tree

Call the depth function recursively
1. if Sub tree/tree is empty then return 0
2. else get maximum depth in left sub tree and right sub tree + 1.

class Tree {
   int value;
   Tree left;
   Tree right;
   public Tree (int value) {
      this.value = value;
   }
}

public class FindMaxDepth {

   private static int depth(Tree tree) {
      if(tree==null) {
         return 0;
      } else {
         return Math.max(depth(tree.left), depth(tree.right)) + 1;
      }
   }

   public static void main(String[] args) {
      Tree root = new Tree(1);
      root.left = new Tree(2);
      root.right = new Tree(3);
      root.left.left = new Tree(7);
      root.left.right = new Tree(6);
      root.right.left = new Tree(5);
      root.right.right = new Tree(4);
      root.left.left.left = new Tree(8);
      root.left.left.right = new Tree(9);
      root.left.left.left.left = new Tree(11);
      root.left.left.left.right = new Tree(10);

      System.out.println(depth(root));
   }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...