Grind 75 Question 22: Diameter of Binary Tree
Ugh. Again with the binary tree.
The 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.
The Initial Attempt
I’m really not feeling this one, and I still have no idea to produce recursion/a depth-first search from scratch. I mess around the balanced binary tree question and come up with this half-assed attempt:
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
function dfs(tree) {
if(tree == null){
return 0;
}
let right = dfs(tree.right);
let left = dfs(tree.left);
let pathLength = 0;
pathLength ++;
return pathLength;
}
return pathLength;
};It doesn’t work (of course) so I visit Neetcode’s solution for enlightenment.
The Solution
var diameterOfBinaryTree = function(root) {
let diameter = 0;
function dfs(tree) {
if(tree == null) return -1;
let right = dfs(tree.right);
let left = dfs(tree.left);
diameter = Math.max(diameter, 2 + left + right);
return 1 + Math.max(left, right)
}
dfs(root)
return diameter;
};I wasn’t far, but I wasn’t close, either. Let’s see if I can explain this one.
- First, we declare diameter as 0, which we will return at the end.
- Then, we create our recursive function:
- First thing we look at is, if the tree is null — return negative one. This somehow balances the equation down below. Ah, okay. It won’t execute if it runs into a negative tree, but we can’t return zero because a zero path is a node itself. So a null tree is -1 on left and right, then we add two later on to balance that out.
- Next thing we do is call the function on the left and right branches, until they’re exhausted.
- Here’s the meat of the recursion, what to do: the new diameter will be the larger number between the current diameter and the left and right plus two.
- Then for some reason we return the longer between left and right and add one — I guess this somehow tells you which is the longer path. I’m honestly slightly baffled at this point but okay.
- Execute the depth-first search on root, return diameter, which, due to all that Math.max() will be the longest diameter. Ba. Boom.
What I Learned
- Um. I guess the good news is, I’m sort of learning the structure of recursion. Sort of. Basically, you operate the function on each side of the tree, then tell the function what it is you actually want it to do. Then you call the whole thing on the tree as a whole and return what you need to. Easier said than done, though.
CategoriesSoftware Dev Journey
2
mins
read
