This week's book giveaway is in the Other Languages forum.
We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!
See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Find Binary Tree Height with O(n/2)

 
Chris Shoban
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 21416
33
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 67
Debian Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
kri shan
Ranch Hand
Posts: 1478
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic