Finding the longest unique paths in a tree

Question

Suppose we have a tree consisting of N nodes. The challenge is to find all the longest unique paths in the tree. For example, if the tree looks like this:

Then in the tree there are three longest unique paths: 1 - 2 - 3 - 4 - 5, 6 - 2 - 3 - 4 - 5 and 1 - 2 - 6.

I want to programmatically find and save all such paths for a given tree. One way to do this is to compute the paths between each pair of node in the tree and then reject the paths that are contained in any other path. However, I am looking for an effective way to do this. My questions are:

• Is it possible to calculate this information less than O (N ^ 2)? I could not come up with a solution that would be faster than O (N ^ 2).
• If so, could you be kind enough to lead me to a decision.

The reason I want to try is because I am trying to solve this problem: KNODES

Answer 1

An algorithm with time complexity below O(N^2) can exist only if each solution for a tree with nodes N can be encoded in less than O(N^2) .

Suppose a complete binary tree with N leaves ( N=n log n ). The solution to the problem will contain a path for each set of 2 sheets. This means that the solution will have elements O(N^2) . Thus, for this case, we can code the solution as 2-element leaf sets.

Now consider an almost complete binary tree with m leaves, which was created by removing only arbitrary leaves from a complete binary tree with leaves N Comparing the solution to this tree with the solution to a complete binary tree, both will share empty pools. In fact, for each subset of the ways to solve a complete binary tree, there will be at least one binary tree with m leaves, as indicated above, which contains all the solutions of such a subset. (We intentionally ignore the fact that a tree with leaves m may have several more paths in the solution, where at least some of the ends of the path are not leaves of a complete binary tree.)

Only this part of the solution for a binary tree with m leaves will be encoded with a number with bits (n^2)/2 . The bit index in this number is an element in the upper right half of the matrix with columns and rows N

For n=4 it will be:

 x012 xx34 xxx5 

The bit with index i will be set if the undirected path row(i),column(i) contained in the solution.

As we have already established, a solution for a tree with leaves m can contain any subset of the solution for a complete binary tree with leaves n>=m , each binary number with bits (n^2)/2 will be a solution for a tree with leaves m .

Now encoding all possible numbers using (n^2)/2 bits with less than (n^2)/2 not possible. So, we have shown that solutions, at least, require a representation of the space O(N^2) . Using N=n log n from above, we obtain a space requirement of at least O(N^2) .

Therefore, there is a doens't algorithm with time complexity less than O(N^2)

Answer 2

As I understand it, you have a tree without a selected root. Your valid paths are paths that prevent you from visiting the tree nodes twice (you are not allowed to return). And you need to find all such valid paths that are not subpaths of any valid path.

So, if I understood correctly, then if a node has only one edge, then the valid path either starts or stops on this node. If the tree is connected, you can get from any node to any node in one valid way.

So, you select all nodes with one edge, call it S. Then select one of S and swipe the whole tree, keeping the paths to the ends (the path, not the walking order). Then you do this with every other element on S and delete the duplicated paths (they can be in the reverse order: for example, starting from 1: 1 - 2 - 6 and starting from 6: 6 - 2 - 1).

So, here you have to visit all the nodes in the tree as many times as you have leaves in the tree. Thus, the complexity depends on the branching factor (in the worst case it is O (n ^ 2). There are some optimizations that can reduce the number of operations, for example, you do not need to walk through the tree from the last of S.

Answer 3

In this figure, the longest paths are {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 3, 6}, {1, 2, 3, 7}, {1, 2, 3, 8}, {1, 2, 3, 9}, {1, 2, 3, 10}

For a tree like this, saving all the long paths will cost you O (N ² )

Answer 4

Suppose you have a binary tree, as in the picture.

 class Node(object): def __init__(self, key): self.key = key self.right = None self.left = None self.parent = None def append_left(self, node): self.left = node node.parent = self def append_right(self, node): self.right = node node.parent = self root = Node(3) root.append_left(Node(2)) root.append_right(Node(4)) root.left.append_left(Node(1)) root.left.append_right(Node(6)) root.right.append_right(Node(5)) 

And we need to get all the paths between all the leaves. So in your tree:

• 1, 2, 6
• 6, 2, 3, 4, 5
• 1, 2, 3, 4, 5

You can do this in (edit: non linear, quadratic) time.

 def leaf_paths(node, paths = [], stacks = {}, visited = set()): visited.add(node) if node.left is None and node.right is None: for leaf, path in stacks.iteritems(): path.append(node) paths.append(path[:]) stacks[node] = [node] else: for leaf, path in stacks.iteritems(): if len(path) > 1 and path[-2] == node: path.pop() else: path.append(node) if node.left and node.left not in visited: leaf_paths(node.left, paths, stacks, visited) elif node.right and node.right not in visited: leaf_paths(node.right, paths, stacks, visited) elif node.parent: leaf_paths(node.parent, paths, stacks, visited) return paths for path in leaf_paths(root): print [n.key for n in path] 

The output for your tree will be as follows:

[1, 2, 6]

[6, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

The idea is to keep track of all visited leaves when traversing a tree. And keep a stack of paths for each sheet. So, here is the trade-off between memory and performance.

Answer 5

Take a tree that looks like a star with nodes n and n-1 .

Then you have C(n-1, 2) unique longest paths.

Thus, the lower limit of complexity cannot be less than O (n ^ 2).

Answer 6

Draw a tree. Let v be a vertex, p be its parent. The length of the longest path, including v, but not p = (height of the left subtree v) + (height of the right subtree v).

The maximum across v is the longest path on the chart. You can calculate this in O (n):

First calculate all the intermediate heights. Start with leaves and process: (height below v) = 1 + max (height below the left child, height below the right child)

Then calculate the sum (height of the left subtree v) + (height of the right subtree v) for each vertex v and take the maximum. This is the length of the longest path on the chart.