Take the 2-minute tour ×

How can we find center of a binary tree? What shall be the most efficient algorithm. Though center of binary tree will be the mid point of the path corresponding to the diameter of tree. We can find the diameter of tree without actually knowing the path, is there any similar technique for finding center of binary tree?

share|improve this question
"The path corresponding to the diameter of tree" - what does this mean? What is the diameter of a binary tree? (Let's use the first image at en.wikipedia.org/wiki/Binary_tree as an example.) –  Oliver Charlesworth Aug 17 '11 at 14:52
diameter is the longest path between two leaf nodes of a tree. So, the center of tree will be middle node of this path. –  user302520 Aug 17 '11 at 14:53
It's a general binary tree, not necessarily a BST. –  user302520 Aug 17 '11 at 14:54
If you know how to find the diameter, and you are saying the "center" is the middle-node of the list in the path between the two leaves that define the diameter, what is the problem? Are you asking if there is an algorithm that will avoid trying to find the diameter first? –  Jason Aug 17 '11 at 14:56
strangely, in a 25 year career as a programmer, not once have I needed to find the centre of a binary tree...Never. –  Mitch Wheat Aug 17 '11 at 14:58

3 Answers 3

If you know the diameter : D

and you know the max depth of the tree : M

then your center will be at the (M-(D/2)) th node(from the root) on the deepest path.(it might be M - (D-1)/2 depending on parity, you need to check yourself)

If you have more than on 1 paths from root to leaf with M nodes then the center is the root. (only true when the longest path goes through the root)


To answer your remark.

if it doesn't go through the root. Let's take the D/2th node on the diameter it will still be on the longest side of the diameter path (wich is in all the cases the longest path from root to leaf). and therefore M-D/2 still represent this point from the root.

Taking M-D/2nth from the root is the same as talking D/2nth from the leaf of the longest path.

Am I clear enough ? You might just want to draw it to check it .

share|improve this answer
I think you are assuming that longest path always pass through root, then this formula might be valid but otherwise, I don't think this is a general formula. –  user302520 Aug 17 '11 at 15:06
@user302520 my last sentence is true only in the case you describe. But the first example still works because the nth is calculated from the root. I'm gona check again. –  Ricky Bobby Aug 17 '11 at 15:16
@user302520 I updated the post –  Ricky Bobby Aug 17 '11 at 15:23
+1 for the hidden emoticon in line 1 –  Peaches491 Aug 17 '11 at 19:47
@RickyBobby how do u go about this problem if the root node doesnt lie on the longest path. can u please explain? –  Sumit Kumar Saha Nov 18 '12 at 20:27

You could calculate this in linear time O(N) by storing a list of the nodes that you have traversed if you are using a recursive method where you calculate the diameter by using the height of the tree (see this website here).

For instance, adapt the linear-time diameter function at the link I posted above so that you are also collecting a list of the nodes you have visited, and not just distance information. On each recursive call, you would select the list that went along with the longer traversed distance. The middle of the list that represented the diameter of the tree would be the "center" of the tree.

Your setup would look like the following:

typedef struct linked_list
    tree_node* node;
    linked_list* next;
} linked_list;

typedef struct list_pair
    linked_list* tree_height;
    linked_list* full_path;
} list_pair;

//some standard functions for working with the structure data-types
//they're not defined here for the sake of brevity
void back_insert_node(linked_list** tree, tree_node* add_node);
void front_insert_node(linked_list** tree, tree_node* add_node);
int list_length(linked_list* list);
void destroy_list(linked_list* list);
linked_list* copy_list(linked_list* list);
linked_list* append_list(linked_list* first, linked_list* second);

//main function for finding the diameter of the tree
list_pair diameter_path(tree_node* tree)
    if (tree == NULL)
        list_pair return_list_pair = {NULL, NULL};
        return return_list_pair;

    list_pair rhs = diameter_path(tree->right);
    list_pair lhs = diameter_path(tree->left);

    linked_list* highest_tree = 
           list_length(rhs.tree_height) > list_length(lhs.tree_height) ? 
                                      rhs.tree_height : lhs.tree_height;

    linked_list* longest_path =
           list_length(rhs.full_path) > list_length(lhs.full_path) ?
                                      rhs.full_path : lhs.full_path;

    //insert the current node onto the sub-branch with the highest height
    //we need to make sure that the full-path, when appending the 
    //rhs and lhs trees, will read from left-to-right
    if (highest_tree == rhs.tree_height)
        front_insert_node(highest_tree, tree);
        back_insert_node(highest_tree, tree);

    //make temporary copies of the subtrees lists and append them to 
    //create a full path that represents a potential diameter of the tree
    linked_list* temp_rhs = copy_list(rhs.tree_height);
    linked_list* temp_lhs = copy_list(lhs.tree_height);
    linked_list* appended_list = append_list(temp_lhs, temp_rhs);

    longest_path =
           list_length(appended_list) > list_length(longest_path) ?
                                      appended_list : longest_path;

    list_pair return_list_pair;
    return_list_pair.tree_height = copy_list(highest_tree);
    return_list_pair.full_path = copy_list(longest_path);


    return return_list_pair;

Now the function returns a series of pointers in the full_path structure member that can be used to cycle though and find the middle-node which will be the "center" of the tree.

P.S. I understand that utilizing copying functions is not the fastest approach, but I wanted to be clearer rather than make something that was faster but had too much pointer-twiddling.

share|improve this answer
Optimized implementation: The above implementation can be optimized by calculating the    
height in the same recursion rather than calling a height() separately.
/*The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. So, function should be used as follows:

int height = 0;
struct node *root = SomeFunctionToMakeTree();
int diameter = diameterOpt(root, &height); */
int diameterOpt(struct node *root, int* height)
/* lh --> Height of left subtree
  rh --> Height of right subtree */
int lh = 0, rh = 0;

/* ldiameter  --> diameter of left subtree
  rdiameter  --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0;

if(root == NULL)
 *height = 0;
 return 0; /* diameter is also 0 */

/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right, &rh);

/* Height of current node is max of heights of left and
 right subtrees plus 1*/
*height = max(lh, rh) + 1;

return max(lh + rh + 1, max(ldiameter, rdiameter));
Time Complexity: O(n)
share|improve this answer

Your Answer

