{"id":4844,"date":"2021-12-13T15:57:52","date_gmt":"2021-12-13T10:27:52","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4844"},"modified":"2022-07-08T15:26:14","modified_gmt":"2022-07-08T09:56:14","slug":"diameter-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/diameter-of-a-binary-tree\/","title":{"rendered":"Tree Diameter &#8211; Diameter of a Binary Tree"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#optimal-approach\">Optimal Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a binary tree, find the diameter of the tree.<\/p>\n\n\n\n<p><strong>Diameter<\/strong>: The diameter of a tree is the length of the <strong>longest path<\/strong> between any <strong>2 nodes<\/strong> of a tree. The length of a path is counted as the number of <strong>edges<\/strong> lying on that path.<\/p>\n\n\n\n<p><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<p><strong>Input 1:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Input 1\"  class=\"wp-image-5024 pk-lazyload\"  width=\"355\"  height=\"355\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 355px) 100vw, 355px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-1024x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-1024x1024.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-300x300.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-150x150.png 150w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-768x767.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-110x110.png 110w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-380x380.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-550x550.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-800x799.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3-1160x1159.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image2-3.png 1221w\" ><\/figure><\/div>\n\n\n\n<p><strong>Output 1:<\/strong> 6<br><strong>Explanation 1:<\/strong> The path of the tree which is the diameter is [7, 5, 2, 1, 3, 6, 8].<\/p>\n\n\n\n<p><strong>Input 2:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5025 pk-lazyload\"  width=\"525\"  height=\"373\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 525px) 100vw, 525px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-1024x727.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-1024x727.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-300x213.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-768x545.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-380x270.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-550x391.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-800x568.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-1160x824.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2.png 1221w\" ><\/figure><\/div>\n\n\n\n<p><strong>Output 2:<\/strong> 3<br><strong>Explanation 2:<\/strong> The diameter path of the tree is [4, 2, 1, 3] or [5, 2, 1, 3].<\/p>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>We note that the diameter of a tree can be written as the <strong>maximum<\/strong> of the diameter of the <strong>left subtree<\/strong> of the current node, the diameter of the <strong>right subtree<\/strong> of the current node, and the <strong>diameter<\/strong> of the current tree. We can recursively calculate the sum of the left and right subtree to get the diameter of the current tree and update the maximum value of diameter by the sum for each node in a recursive manner using <strong>DFS<\/strong>.<\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n *\/\nclass Solution {\npublic:\n    int getDepth(TreeNode *root) {\n        if(root == NULL) {\n            return 0;\n        }\n        int leftSubtreeDepth = getDepth(root->left);\n        int rightSubtreeDepth = getDepth(root->right);\n        return max(leftSubtreeDepth, rightSubtreeDepth) + 1;\n    }\n    int diameterOfBinaryTree(TreeNode* root) {\n        if(root == NULL) {\n            return 0;\n        }\n        int leftSubtreeDiameter = diameterOfBinaryTree(root->left);\n        int rightSubtreeDiameter = diameterOfBinaryTree(root->right);\n        int diameter = getDepth(root->left) + getDepth(root->right);\n        diameter = max(diameter, max(leftSubtreeDiameter, rightSubtreeDiameter));\n        return diameter;\n    }\n};<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n *\/\nclass Solution {\n    int getDepth(TreeNode root) {\n\t\tif(root == null) {\n\t\t\treturn 0;\n\t\t}\n\t\tint leftSubtreeDepth = getDepth(root.left);\n\t\tint rightSubtreeDepth = getDepth(root.right);\n\t\treturn Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;\n\t}\n    public int diameterOfBinaryTree(TreeNode root) {\n        if(root == null) {\n\t\t\treturn 0;\n\t\t}\n\t\tint leftSubtreeDiameter = diameterOfBinaryTree(root.left);\n\t\tint rightSubtreeDiameter = diameterOfBinaryTree(root.right);\n\t\tint diameter = getDepth(root.left) + getDepth(root.right);\n\t\tdiameter = Math.max(diameter, Math.max(leftSubtreeDiameter, rightSubtreeDiameter));\n\t\treturn diameter;\n    }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def getDepth(self, root):\n        if not root:\n            return 0\n        leftSubtreeDepth = self.getDepth(root.left)\n        rightSubtreeDepth = self.getDepth(root.right)\n        return max(leftSubtreeDepth, rightSubtreeDepth) + 1\n    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n        if not root:\n            return 0;\n        leftSubtreeDiameter = self.diameterOfBinaryTree(root.left);\n        rightSubtreeDiameter = self.diameterOfBinaryTree(root.right);\n        diameter = self.getDepth(root.left) + self.getDepth(root.right);\n        diameter = max(diameter, max(leftSubtreeDiameter, rightSubtreeDiameter));\n        return diameter;<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(n^2)<br><strong>Space Complexity:<\/strong> O(1) \/\/ If recursion stack space is ignored<\/p>\n\n\n\n<h2 id=\"optimal-approach\">Optimal Approach<\/h2>\n\n\n\n<p id=\"the-idea-for-the-optimal-approach-is-the-same-as-that-for-the-naive-approach-however-in-the-optimal-approach-we-change-the-implementation-such-that-the-calculation-for--depths-of-the-subtrees--and-the--maximum-diameter-of-the-tree--is-done-in-the-same-recursive-function-simultaneously-to-optimize-the-time-complexity\">The idea for the optimal approach is the same as that for the naive approach. However, in the optimal approach, we change the implementation such that the calculation for <strong>depths of the subtrees<\/strong> and the <strong>maximum diameter of the tree<\/strong>, is done in the same recursive function simultaneously to optimize the time complexity.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n *\/\nclass Solution {\npublic:\n    int getMaxDepth(TreeNode* root, int &amp;diameter) {\n        if(root == NULL) {\n            return 0;\n        }\n        int leftSubtreeDepth = getMaxDepth(root->left, diameter);\n        int rightSubtreeDepth = getMaxDepth(root->right, diameter);\n        diameter = max(diameter, leftSubtreeDepth + rightSubtreeDepth);\n        return max(leftSubtreeDepth, rightSubtreeDepth) + 1;\n    }\n    int diameterOfBinaryTree(TreeNode* root) {\n        int diameter = 0;\n        getMaxDepth(root, diameter);\n        return diameter;\n    }\n};<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n *\/\nclass Solution {\n    static int diameter;\n\tint getMaxDepth(TreeNode root) {\n\t\tif(root == null) {\n\t\t\treturn 0;\n\t\t}\n\t\tint leftSubtreeDepth = getMaxDepth(root.left);\n\t\tint rightSubtreeDepth = getMaxDepth(root.right);\n\t\tdiameter = Math.max(diameter, leftSubtreeDepth + rightSubtreeDepth);\n\t\treturn Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;\n\t}\n    public int diameterOfBinaryTree(TreeNode root) {\n        diameter = 0;\n\t\tgetMaxDepth(root);\n\t\treturn diameter;\n    }\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    diameter = 0\n    def getMaxDepth(self, root):\n        if not root:\n            return 0\n        leftSubtreeDepth = self.getMaxDepth(root.left)\n        rightSubtreeDepth = self.getMaxDepth(root.right)\n        self.diameter = max(self.diameter, leftSubtreeDepth + rightSubtreeDepth)\n        return max(rightSubtreeDepth, leftSubtreeDepth) + 1\n    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n        self.diameter = 0\n        self.getMaxDepth(root)\n        return self.diameter<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N)<br><strong>Space Complexity:<\/strong> O(1) \/\/ If recursion stack space is ignored.<\/p>\n\n\n\n<p><strong>Practice Problem &#8211;<\/strong> <a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/largest-distance-between-nodes-of-a-tree\/\" target=\"_blank\">Largest Distance Between Nodes of a Tree<\/a><\/p>\n\n\n\n<h2 id=\"additional-resources\">Additional Resources<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/courses\/programming\/tree-data-structure\/binary-tree\/\" target=\"_blank\">Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/top-view-of-binary-tree\/\" target=\"_blank\">Top view of Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/level-order-traversal\/\" target=\"_blank\">Level Order Traversal of Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/bottom-view-of-binary-tree\/\" target=\"_blank\">Bottom View of Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/inorder-traversal-of-a-binary-tree\/\" target=\"_blank\">Inorder Traversal of a Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/left-view-of-a-binary-tree\/\" target=\"_blank\">Left View of a Binary Tree<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a binary tree, find the diameter of the tree. Diameter: The diameter of a tree&hellip;\n","protected":false},"author":5,"featured_media":5023,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[674],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4844"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4844"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4844\/revisions"}],"predecessor-version":[{"id":10288,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4844\/revisions\/10288"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5023"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}