Popular Posts

  • Robot in an NXN grid
    Problem: Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. ...
  • CLRS Exercises 2.3-4 Recursive insertion sort
    Problem: Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n], we recursively sort A[1 n -1] ...
  • Kth Largest from an infinite stream
    Problem:   Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if...
  • Print BST keys in the given range
    Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i....
  • Simultaneous minimum and maximum
    How many comparisons are necessary to determine the minimum of a set of n elements? n-1 comparisions. It is not difficult to devise an ...
  • CLRS Exercises 2.3-7
    Problem: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exi...
  • Delete alternate nodes of a Linked List
    Problem: Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked lis...
  • Print Ancestors of a given node in Binary Tree
    Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the give...
  • CLRS - Problem 2.1
    Problem: Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in i...
  • CLRS Exercises 5.1-2
    Problem: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running tim...

Wednesday, August 10, 2011

Diameter of a binary tree

Problem:
Find the diameter of a binary tree.
Solution:

  1. Do Post order traversal
  2. if Left Max path + Right Max path > Max then
  3. Max = Left Max path + Right Max path 
  4. return 1 + MAX(Left Max path length + Right Max path length)

Complexity: O(n), where n = no of nodes
Code:

Posted by anantha at 8/10/2011 03:24:00 PM
Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)