This week's giveaway is in the EJB and other Java EE Technologies forum.
We're giving away four copies of EJB 3 in Action and have Debu Panda, Reza Rahman, Ryan Cuprak, and Michael Remijan on-line!
See this thread for details.
The moose likes Performance and the fly likes Find Binary Tree Height with O(n/2) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Find Binary Tree Height with O(n/2)" Watch "Find Binary Tree Height with O(n/2)" New topic
Author

Find Binary Tree Height with O(n/2)

Chris Shoban
Greenhorn

Joined: Nov 10, 2010
Posts: 1
Given a binary tree (balanced or in-balanced), write the code to find the tree's height in O(n/2).

So I was given this for an interview question the other day. I was told that O(n) is the easy answer, but they wanted to see how I would improve the algorithm. It is stuck in my head as I could only discuss the O(n) solution, starting from the root and recursively checking the left and right child node while increasing the count. Yet since this would traverse every node, the run time is O(n). The other possible solution that I offered, which do not suffice, is to somehow know whether the left or right sub-tree is somehow longer and traverse only that sub-tree, therefore only checking half the nodes. Another option I tried to argue, is if the system runs on a dual-core (or multiple core), one core could be used for the left sub-tree and find it's height and another core would be used for the right sub-tree and the time is cut in half since each core works on half a binary tree.

Another confusion for me, is I thought O(n) == O(n/2) as 1/2 is the leading constant which would be disregarded.

Is it possible to find the height with a speed faster than O(n)?

Any thoughts?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18124
    
    8

Chris Shoban wrote:Another confusion for me, is I thought O(n) == O(n/2) as 1/2 is the leading constant which would be disregarded.


Yes, that's exactly correct. Perhaps they meant something else?
Mike Peters
Ranch Hand

Joined: Oct 10, 2009
Posts: 67

For a balanced tree the depth of the tree is log2(N) you don't need an algorithm for that. For an non-balanced tree the depth is between log2(N) and N. You can only calculate this with an O(N) algorithm if your data structure does not contain any additional depth information.


Mike Peters
kri shan
Ranch Hand

Joined: Apr 08, 2004
Posts: 1368
For a balanced tree the depth of the tree is log2(N) you don't need an algorithm for that. For an non-balanced tree the depth is between log2(N) and N. You can only calculate this with an O(N) algorithm if your data structure does not contain any additional depth information.


How to find the depth of a non balanced binary tree's from root node ? (Which algorithm gives best performance)
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Find Binary Tree Height with O(n/2)
 
Similar Threads
tree datastructure algorithm
fast searching in large text files
How will you find if a binary tree is fully balanced?
Algorithm to find Nodes having largest distance in Binary tree.
What is the difference between balanced binary trees and binary space partition trees