Binary Tree: The Diameter.
David PynesBlockedUnblockFollowFollowingJan 28In search of the longest path.
WhyOften computer scientists wonder if a problem is solvable, and if it is solvable, how can the problem be solved better?For example, consider finding the longest path in an unrestricted graph.
How long is this path?It turns out finding the longest path in this graph, where vertices repeat, is pretty difficult.
When there is a loop, there can always be a longer path.
So we consider this problem to be NP-hard.
(A group of problems that one day could be solved, but at this point in time have not yet been solved.
)Interestingly though, if we restrict the problem to a DAG, such as the binary tree, the longest path problem now becomes solvable.
WhatThat is what this article is all about, the search to ascertain the diameter.
The diameter of a binary tree is the length of the longest path.
For example, this DAG has a diameter of six:There are two ways to go about solving this problem.
The method of brute force.
The method of dynamic programming.
Brute force is all about exhausting all combinations to arrive at a solution.
The benefit of brute force is that it is easy to implement, and for that reason also easy to understand.
The drawback is that you run the risk of a combinatorial explosion, when a small change creates a rapid growth in complexity.
With brute force the algorithm travels all leaf-to-leaf paths, then arrives at the diameter.
This approach is both explicit and repetitive.
Notice how the algorithm travels paths that it has already been down before?This begs an important question, is there a way to encode an algorithm that remembers where it came from?If so, can we circumvent having to repeatedly go down the same paths?Dynamic programming sequences sub-problems together, having each sub-problem lead to the solution.
With dynamic programming we no longer have to visits paths we’ve been down before, instead we can prune the shorter branches and track the diameter at each step.
With the dynamic approach the algorithm travels down the tree and counts lengths on the way back up.
The algorithm’s elegance is first displayed when it arrives at the node 75, there the sub-problem is clearly defined.
Here a decision must be made, prune left or right.
Since the right branch is a length of one and the left branch is a length of two, the right branch gets pruned.
The algorithm now knows to never go down the right path again.
Later on the algorithm travels down the other side of the tree.
Counting lengths and pruning branches accordingly, from node 125 which branch is smaller?This time the left branch is smaller.
So, the left branch gets a pruning.
At each iteration the algorithm checks if a longer diameter is found.
On the last iteration the diameter updates.
The search is complete and the length of the longest path is found.
Note, unlike the previous example(s), the algorithm does not have to find a diameter at the root of the tree.
Note the image below.
HowLet’s now examine the code.
int find_diameter(node* n, int& dmtr) { if(!n) return 0; int left = find_diameter(n->left,dmtr); int right = find_diameter(n->right, dmtr); if(left + right > dmtr) sol = left + right; if(left > right) return 1 + left; else return 1 + right;}Dynamic programming is dense and riddled with nuances.
The function parameters:int find_diameter(node* n, int& dmtr) { }find_diameter requests a node to traverse the tree and a int& to store and update the diameter.
2.
The base case:if(!n) return 0;Dynamic programming uses recursion.
The technique of recursion has two requirements 1) a base case, 2) an iterator.
The base case sets a necessary boundary.
The base case here is when the iterator travels beyond the leafs.
If so trigger the base case, stop iterating, the branch is a length of zero.
3) The iterator:int left = find_diameter(n->left, dmtr);int right = find_diameter(n->right, dmtr);The iterator iterates using a post-order traversal to the left, then to the right, and then to the root.
Notice, the return value from the n->left traversal is int left, representing the length from the left branch.
The same logic is applied to the right branch.
4.
Storing the diameter:if(left + right > dmtr) dmtr = left + right;If the algorithm finds a longer diameter, update the diameter.
5.
The sub-problem:if(left > right) return 1 + left;else return 1 + right;At each iteration, when the function returns, prune the smaller branch and add one to the branch length.
This last statement indicates to the previous call from the call stack which branch is longer.
In other words, the values at the bottom of the tree add to the lengths of the nodes higher up the tree, via the return.
For that reason, this code uses a bottom-up approach.
ConclusionBy solving sub-problems and calculating lengths along the way, the diameter can be found in O(n) linear time.
This technique is both elegant and efficient.
The lesson here; define a reoccurring sub-problem, solve at each step, use the result of the previous steps to arrive at a concise solution.
For the full C++ program follow the instruction below.
Copy the full source code here and save as main.
cppCompile from the command line, g++ main.
cpp -o Diameter.
exeThen execute the code from command line, .
/Diameter.
exThe codeView the full C++ code: here.
Create a visual on the web app: here.
.. More details