DEV Community is a community of 787,570 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. 30-Day LeetCoding Challenge: Diameter of Binary Tree

Solution:

It asks us to find a binary tree diameter, it also explains to us that is the diameter of a binary tree is the length of the longest path between any two nodes in a tree.

It is also indicated that doesn't matter if the path passes by the root or not.

So, we need to calculate the depth of each node in the tree and then find the longest path between the nodes.

First the depth of node can be found by node.depth = max(node.left.depth, node.right.depth) + 1.

Also, the path always will be the depth of the left subtree + the depth of the right subtree, so on each node, we need to choose the maximum value that takes us to the final answer so our answer will be: diameter = max(diameter, left_depth + right_depth).

So, how we can calculate that if you look to the illustration above we see that we need to go deep to the tree to get one node depth which means we need to use depth-first search DFS.

We use DFS to find the left subtree depth then find the right subtree depth and later choose between them.

• Pseudocode:

• diameterOfBinaryTree(root)

2. call find_depth_helper(root) with the root to find the longest path.
• find_depth_helper(node)
1. if the node is None return 0
2. find_depth_helper(node.left) --> left_depth
3. find_depth_helper(node.right) --> right_depth