This week's giveaway is in the Spring forum.
We're giving away four copies of Microservices Testing (Live Project) and have Chris Love & Andres Sacco on-line!
See this thread for details.
Win a copy of Microservices Testing (Live Project) this week in the Spring forum!
  • 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
  • Tim Cooke
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Liutauras Vilda
  • Henry Wong
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Mikalai Zaikin
  • Himai Minh

need help with binary search tree

 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just started programming in general and started with Java, in an assignment I got I need to find the longest increasing path of a binary search tree of integer. however I have no idea how to carry it out. I know how to count the longest path of a binary search tree, just not when you need to find the path that's the longest with the values increasing.

the part I am stuck with is that my code only counts the longest path of the right of the root node
 
Bartender
Posts: 2700
IntelliJ IDE Opera
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
With your solution do you keep the following tree in mind:


You need something to define what a path in a tree is. You could keep track of the nodes or the start and end node.
 
Saloon Keeper
Posts: 14081
319
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Jack, do you have a binary search tree, or just a simple binary tree?

If the former, then the longest increasing path would simply be the path from the root to the rightmost leaf.

However, if it's not a search tree, then you will have to call the method recursively on both subtrees.
 
jack web
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Jack, do you have a binary search tree, or just a simple binary tree?

If the former, then the longest increasing path would simply be the path from the root to the rightmost leaf.

However, if it's not a search tree, then you will have to call the method recursively on both subtrees.



I am guessing it would be just a binary tree, with what i wrote i cant really figure out how to solve a method in case of


in this case the longest should be 3 (with 5->7->8->9) but my code will return 2 (with 10->12->13)
 
Marshal
Posts: 76070
362
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This question is too difficult for "beginning", so I shall move it.
 
jack web
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
out of curiosity what is the cost of find the leaves in a binary tree in big O notation
 
Stephan van Hulst
Saloon Keeper
Posts: 14081
319
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's a tip:

For any binary tree, the length of the longest increasing path would be the length of the longest increasing path of either the left subtree, or the right subtree, whichever is bigger, plus 1 if the path starts at the root of the subtree, and the root of the parent is smaller than the root of the subtree.

Here are some helper method you could use:
 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Done!
reply
    Bookmark Topic Watch Topic
  • New Topic