Print the Longest leaf-to-leaf path in a binary tree along with its length

I am solving a problem in which I have to find the longest leaf-to-leaf path in a binary tree along with its length.

for example, if the Binary tree is as follows:

         a
         /\
        b c
      /   / \
     d   e  f 
    / \      \
   g  h      p
       \
        k

The longest leaf-to-leaf path would be k-h-d-b-a-c-f-p which is of length 8.

I am calculating the length by recursively finding the length of the left and right sub-tree and then return height_left + height_right + 1 . Is my concept correct?.

Also how should I print the longest leaf-to-leaf path? I just want an idea to proceed.

Answers


It seems to me that this algorithm is very close to finding a diameter of a binary tree. Diameter of the tree is the number of nodes on the longest path between two leaves in the tree.

I think you can look here for the implementation: http://www.geeksforgeeks.org/diameter-of-a-binary-tree/ and then adapt it or optimize it's time complexity if you want. But i think O(n) is good enough.


Most answers on the net gives how to find diameter of a tree, i.e How to find the number of nodes in the longest path.

The only addition is we need to store the nodes which contribute to it.

In recursion, this can be done in two ways.

a) It should be a return type b) It should be an input parameter which is an object. This object is populated with the result during the course of recursion.

Without the need to print the longest path, we only need to check at every node: Max of 1) Left node max path 2) Right node max path c) Current node max path (requires more inputs)

Now, to calculate current node max path, we need more inputs:

Current node max path needs:

1) Max left node height 2) Max right node height

This can either be stored in the node itself (as height parameter) or can be passed with the recursion.

This will only give diameter/length of the longest path.

Now, to get the path printed, we need to store more info which is: - List<Nodes> pathList - This contains the nodes which form the longest path so far (Note this may not contain the current node). - List<Nodes> heightList - This contains the nodes which form the longest height from the node to its leaf.

Finally the algo:

//Inputs and Outputs of the method

class Node{
int value;
Node leftchild;
Node rightchild;
}
class ReturnInfo{
ReturnInfo(){
 maxpathlen = 0;
 maxheight = 0;
 pathList = new ArrayList<Node>();
 heightList = new ArrayList<Node>();
}

int maxpathlen; //current max path
int maxheight; //current max height
List<Nodes> pathList;
List<Nodes> heightList;
}

//Signature public ReturnInfo getMaxPath(Node n);

//Implementation

public ReturnInfo getMaxPath(Node n){
//Base case
if(n==null) return new ReturnInfo();
//This is a bottom up recursion. Info will flow from leaves to root.
//So first recurse and then do the work at this node level
//Recurse left & right
ReturnInfo leftReturnInfo = getMaxPath(n.leftchild);
ReturnInfo rightReturnInfo = getMaxPath(n.rightchild);

//Do work in this recursion or for this node 
ReturnInfo retInfo = new ReturnInfo();

//Update all 4 parameters of returninfo and we are done

retInfo.maxheight = max(leftReturnInfo.maxheight, rightReturnInfo.maxheight) + 1;
//Update retInfo.heightList accordingly
retInfo.heightList = ....

retInfo.maxPathLen = max(leftReturnInfo.maxPathLen, rigthReturnInfo.maxPathLen, leftReturnInfo.maxHeight+rightReturnInfo.maxHeight+1);

//Remember from where maxPathLen came from and update accordingly
retInfo.pathList = .....

return retInfo;//We are done 

}

You need a function that returns longest branch in a subtree and the longest path:

PS: I am leaving out details (Eg. Boundary conditions and so on). But this should give you an idea. This function returns two things 'branch' and 'path'. 'branch' is the longest path from this node to any of its leaves. 'path' is the longest path between any two leaves in this subtree.

def longestPath(node):
    (leftBranch, leftPath) = longestPath(node.left);
    (rightBranch, rightPath) = longestPath(node.right);
    if len(rightBranch) > len(leftBranch):
        curBranch = rightBranch+node.name
    else:
        curBranch = leftBranch+node.name

    curPath = leftBranch + node.name + rev(rightBranch)
    bestPath = curPath
    if len(leftPath) > length(bestPath):
        bestPath = leftPath
    if len(rightPath) > length(bestPath):
        bestPath = rightPath

    return (curBranch, bestPath)

defintion:
node: (char content, node left , node right , node parent)
add(list , node): add node as last element in list
remove(list , index): remove and return element at index in list
length(string): length of string
insert(string , char , index): insert char at index in string
concat(string a , string  OR char b): append b to a

input: node start
output: string

start
list nodes
node n

add(nodes , start)

do
    n = remove(nodes , 0)

    if n.parent != null
        add(nodes , n.parent)
    if n.left != null
        add(nodes , n.left)
    if n.right != null
        add(nodes , n.right)
while !isEmpty(nodes)

//n now is the node with the greatest distance to start
string left = ""
string right = ""

node a = start
node b = n

while(a != b)
     insert(left , a.content , length(left) - 1)
     insert(right , b.content , 0)

     a = a.parent
     b = b.parent

string result = left
concat(result , a.content)
concat(result , right)

return result

Here is my Scala solution (Tree.scala):

/** Searches for the longest possible leaf-to-leaf path in this tree.
 *
 * Time - O(log^2 n)
 * Space - O(log n)
 */
def diameter: List[A] = {
  def build(t: Tree[A], p: List[A]): List[A] = 
    if (t.isEmpty) p
    else if (t.left.height > t.right.height) build(t.left, t.value :: p)
    else build(t.right, t.value :: p)

  if (isEmpty) Nil
  else {
    val ld = left.diameter
    val rd = right.diameter
    val md = if (ld.length > rd.length) ld else rd
    if (1 + left.height + right.height > md.length)
      build(right, value :: build(left, Nil).reverse).reverse
    else md
  }
}

The idea is quite simple:

  1. We recursively search for diameters in children (ld and rd and maximum 'md').
  2. Check whether the longest possibe path that goes through current node is greather then diameters of its children or not (if (1 + ....)).
  3. If its greater then we just need to build a new path with build function, which bilds a longest path from given node 't' to leaf. So, we just concatenates two resuts of this function (for left and right child) with current node.
  4. If its not greater then the diameter is found it is md.

Longest leaf to leaf path means finding diameter of a tree. It can be done using height function.

There are many solutions available online.


Here is my Swift solution:

  func diameterPath() -> [T] {
    return diameterPathHelper(root).Path
  }

  typealias HeightAndDiameterAndPath = (Height: Int, Diameter: Int, Path: [T])

  private func diameterPathHelper(node: TreeNode<T>?) -> HeightAndDiameterAndPath {

    guard let node = node else {
      return HeightAndDiameterAndPath(0, 0, [])
    }

    let left  = diameterPathHelper(node.left)
    let right = diameterPathHelper(node.right)

    let height   = max(left.Height, right.Height) + 1

    if left.Height + right.Height + 1 > max(left.Diameter, right.Diameter) {

      let currentDiameter = left.Height + right.Height + 1
      let path = left.Path + [node.data] + right.Path
      return HeightAndDiameterAndPath(height, currentDiameter, path)

    } else {
      if left.Diameter > right.Diameter {
        return HeightAndDiameterAndPath(height, left.Diameter, left.Path)
      } else {
        return HeightAndDiameterAndPath(height, right.Diameter, right.Path)
      }
    }
  }

We can use the maxdepth approach for this and initialize a variable max as 0.

public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return max;
}

private int maxDepth(TreeNode root) {
    if (root == null) return 0;

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);

    max = Math.max(max, left + right);

    return Math.max(left, right) + 1;
}

}


You have neglected one condition: What if the longest path doesn't pass through the root node?

static int findLongestPathLength(Node root){
     if(root == null)
         return 0;
     int lh = getHeight(root.left);
     int rh = getHeight(root.right);
     return Math.max(1+lh+rh,
             Math.max(findLongestPathLength(root.left),findLongestPathLength(root.right)));

 }
static int getHeight(Node root){
     if(root == null)
         return 0;
     return Math.max(getHeight(root.left)+1, getHeight(root.right)+1);
 }

This will also make sure it find the longest path even if it doesn't pass through root.


Need Your Help

Remember original page to redirect to with spring security after a failed login on unprotected URL

java login struts2 spring-security

I'm using spring-security and struts 2. Most of our pages have content that is unprotected mixed with some protected content (user controls) so it is not like the examples where you go to a certain...

Integration services project Templates missing in VS 2015

sql-server visual-studio-2015 ssis-2012 sql-server-data-tools sql-server-2016

I am trying to create Integration services project in VS 2015. i Installed the SQL Server Data Tools for VS 2015. i also installed SQL Server 2016.