jack web

Greenhorn

Posts: 5

posted 6 years ago

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

the part I am stuck with is that my code only counts the longest path of the right of the root node

posted 6 years ago

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.

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.

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler

Please correct my English.

Stephan van Hulst

Saloon Keeper

Posts: 6981

110

posted 6 years ago

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.

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.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

jack web

Greenhorn

Posts: 5

posted 6 years ago

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)

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)

Campbell Ritchie

Sheriff

Posts: 53779

128

jack web

Greenhorn

Posts: 5

Stephan van Hulst

Saloon Keeper

Posts: 6981

110

posted 6 years ago

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:

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: