Recursive Depth First Search Algorithm to Compute the Diameter o

  • Time：2020-09-10 12:55:33
  • Class：Weblog
  • Read：35

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].

Compute the Diameter of a Binary Tree using Recursive Depth First Search Algorithm

The diameter can be computed as the depth of the left subtree plus the depth of the right subtree. However, as the diameter may not go through the root, it may exist in sub problems i.e. left or right tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, dfs(root)));
    }
    
private:
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        return depth(root->left) + depth(root->right);  
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, dfs(root)));
    }
    
private:
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        return depth(root->left) + depth(root->right);  
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
};

The following is a shorter implementation that gets rid of a intermediate DFS function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) +depth(root->>right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(depth(root->left), depth(root->right));
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) +depth(root->>right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(depth(root->left), depth(root->right));
    }
};

The C++ Depth First Search Algorithm is implemented using Recursion. We’ve noticed that the depth function is called many times for a same Tree Node, thus we can use a hash map to store the values for the visited nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) + depth(root->right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (data.find(root) != data.end()) return data[root];
        int r = 1 + max(depth(root->left), depth(root->right));
        data[root] = r;
        return r;
    }
 
private:
    unordered_map<TreeNode*, int> data;    
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) + depth(root->right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (data.find(root) != data.end()) return data[root];
        int r = 1 + max(depth(root->left), depth(root->right));
        data[root] = r;
        return r;
    }

private:
    unordered_map<TreeNode*, int> data;    
};

However, the above Recursive DFS is not optimal as we may visit a node more than once. We can compute the diameter on the fly when we compute the depth of the binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans;
    }
    
    int depth(TreeNode* root) {
        if (!root) return 0;
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans, L + R);
        return max(L, R) + 1;
    }
 
private:
    int ans;
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans;
    }
    
    int depth(TreeNode* root) {
        if (!root) return 0;
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans, L + R);
        return max(L, R) + 1;
    }

private:
    int ans;
};

And the time complexity is O(N) where N is the number of the nodes in the binary tree. The space requirement is also O(N) due to implicit usage from Recursive calls.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
China opposes politicization, instrumentalization of counterterr
China approved major projects worth 1.5 trln yuan by end-Novembe
Head coach of Qiongzhong women’s football team thanks Messi, Ini
Opening ceremony of high-level segment of second part of COP15 m
Renhuai-Zunyi Expressway in SW China officially put into full op
A glimpse of headquarters of National Archives of Publications a
Who Xi met during his visit to Saudi Arabia
The bustling vibes in China: Aerial Shanghai after COVID-19 rest
Explore a hidden thousand-year-old ethnic village
Ice harvesting
Share：Facebook Twitter
Comment list
Comment add