• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Find Binary Tree Height with O(n/2)

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Ranch Hand
Posts: 67
Eclipse IDE Debian Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 1491
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)
 
I carry this gun in case a vending machine doesn't give me my fritos. This gun and this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic