Diameter of Binary Tree
Problem
Given the
root
of a binary tree, return 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
.The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2] Output: 1
Pseudocode
- longest path is the left most node travelling to the right most node.
- traverse the longest path left + longest path right
Solution
var diameterOfBinaryTree = function(root) {
let maxDistance = 0
function walk(node) {
// base condition
if(!node) {
return 0
}
const leftWalk = walk(node.left)
const rightWalk = walk(node.right)
maxDistance = Math.max(leftWalk + rightWalk, maxDistance)
return Math.max(leftWalk + 1, rightWalk + 1)
}
walk(root)
return maxDistance
};
Time and Space Complexity
Time
Complete traversal of the tree - O(N)
Total - O(N)
Space
Memory requirements increase linearly for each recursion stack - O(N)
Total - O(N)
Last updated