Diameter in a binary tree

--Originally published at Enro Blog

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) ))

Continue reading "Diameter in a binary tree"

Best Time to Buy and Sell Stock II

--Originally published at Enro Blog

I joined leet code 30 days of code challenge and this is the 5th challenge. I would like to give some of the insight I found while solving this problem with swift. The problem as follows.

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

The first approach consist in taking advantage of the moment we find a valley and immediately after take into account its adjacent peak. now we add the difference.

class Solution {
    func maxProfit(_ prices Continue reading "Best Time to Buy and Sell Stock II"