Diameter in a binary tree

Problem

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

The length of the diamer of the binary tree can pass through the root of the binary tree or not.
In case that it passes.
The diameter is the height of the left subtree + the height of right subtree + 1 that is the root.
height of the left subtree + the height of right subtree + 1
is it not necesary that the path of the diameter passes throught the root.
In case that it dosn’t passes.
You need to calculate the diameter of the left and right subtree and the right subtree.
Now lets consider the new tree, for the new tree ldiameter will be the height of the left subtree. and repeat for rdiameter.
if it does not pass throught root we need to pass the left subtree and right subtree through the recursive function. and out of that leftsubtree and right rubstring reconsider the greater and pick that one.
height of the left subtree + the height of right subtree + 1,
max (ldiameter, rdiameter) )
you have to calculate both of this scenarios because we are not sure wheter or not we pass throught the root.
max(height of the left subtree + the height of right subtree + 1,
max (ldiameter, rdiameter) ))

solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        guard root != nil else{return 0}
        return diameter(root: root)
    }
    func diameter(root: TreeNode?) -> Int {
        guard root != nil else{return 0}
        var rootDiameter:Int = heightOfBinaryTree(root: root?.left) + heightOfBinaryTree(root: root?.right) + 1
        print("\(rootDiameter)")
        var leftDiameter:Int = diameter(root: root?.left)
        var rightDiameter:Int = diameter(root: root?.right)

        return max(rootDiameter, max(leftDiameter, rightDiameter))
    }
    
    func heightOfBinaryTree(root: TreeNode?) ->Int {
        if(root == nil){
            return 0
        }else{
            return max(heightOfBinaryTree(root: root?.left), heightOfBinaryTree(root: root?.left)) + 1
        }
    }
    
}

reference

https://leetcode.com/explore/other/card/30-day-leetcoding-challenge/529/week-2/3293/

 

Author: enroblog

Computer science student at ITESM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s