CODEWITHSUNDEEP
algorithmdata-structurestreebinary-tree
Pavithran Ravichandiran
Pavithran Ravichandiran

Reputation: 1891

How find the longest consecutive path in a binary tree

I was asked in an interview this question. Consider a binary tree, we need to print the length of the longest path, where each element differs by 1.

EG:

          6
        /   \  
      5       7
     / \     / \
    2   4   8   9

answer: 5 ( 4,5,6,7,8 )

How to do this? I developed an algoirthm to print increasing path from root to leaf, but I was not to develop one that keeps track of path that's on both subtrees.

EDIT: Need to get back the original tree after modification.

Upvotes: 0

Views: 1173

Answers (4)

displayName
displayName

Reputation: 14379

The answer is incorrect - another user correctly pointed out a bug. My solution below works only when the max length path passes through the root. In case, for example, the max length path is entirely in the left subtree and does not pass through the root, this answer fails. Feel free to read further to acquaint yourself with a recursive solution... and the bug in it.

I'm assuming that it is not important that the path has to have a difference of +1 as shown in your example. A difference of -1, resulting in a path like 4 -> 5 -> 4 -> 3 -> 4 -> 5 is ok as well.

public int getLongestConsecutivePath(TreeNode root) {
    return root == null
        ? 0
        : getLength(root.left, root.value) + getLength(root.right, root.value);
}

private int getLength(TreeNode node, int prevVal) {
    return node == null || Math.abs(node.value - prevVal) > 1
        ? 0
        : Math.max(getLength(node.left, node.value), getLength(node.right, node.value)) + 1;
}

Explanation:

  • If the root is not null, we get the max length in left and right subtree and sum it.
  • To get max length in a subtree, we recursively get the max length of right and left subtree of the subtree.
    • If we have reached the leaf OR if we have reached a node where the difference in value is greater than 1, we return 0.
    • Else we recursively get the max length from the left and right subtree and add 1 to it to accommodate for this node itself.

Upvotes: 1

CodingPill
CodingPill

Reputation: 31

Let longest_desc[a] be the longest 1-by-1 descending path going down from a Similarly longest_asc[a], the longest 1-by-1 incremental path going down from a

For a fixed root R, the answer would be longest_desc[R] + longest_asc[R] - 1.

A brut force solution would do 2 dfs/bfs traversals from each node X to compute longest_asc[X] and longest_desc[X] and then merge them together. The resulting runtime complexity would be O(n^2).

But we can actually do better using dynamic programming:

longest_asc[X] = max(longest_asc[Y in children[X]] with Y = X + 1)
longest_desc[X] = max(longest_desc[Y in children[X]] with Y = X - 1)

Then we can compute all the values in a single DFS traversal => O(n) solution.

Upvotes: 1

marvel308
marvel308

Reputation: 10458

As suggested by @qwertyman in the comments

  1. remove all invalid edges i.e edges whose difference is greater than 1

  2. Now we have a forest, for each forest calculate the diameter as it is given in @Filip Kočica solution

  3. The answer would be the max diameter out of all forests

Upvotes: 2

Matt Timmermans
Matt Timmermans

Reputation: 59144

For each subtree, you can calculate the longest increasing path down from the subtree root, the longest decreasing path down, and the longest internal path consisting of the increasing and decreasing paths down from the same node anywhere in the subtree.

It's easy to calculate these for a node if you already have them for all of its children, so you can do it as part of any postorder traversal.

The answer is the longest internal path within the whole tree.

Upvotes: 1

Related Questions