Diameter of Tree | Rust
Write a function that takes in a Binary Tree and return its diameter.
The Diameter of a binary tree is defined as the length of its longest path, even if that path doesn’t pass through the root of the tree.
The length of a path is the number of edges between the path’s first node and its last node.
We will use the Depth First Search to Traverse every node of the Input Binary Tree.
Every Node holds two information Current Diameter and Current Height
As we Know the Height and child diameters we can calculate the diameter of the current node.
Current Diameter = MAX( left diameter, right diameter, length of longest path )
Our Base case of Recursion is (0,0) current height and current diameter, as we have reached a None child.
We keep track of the parent nodes in the call stack and as we climb back up we update the current diameter and current height information for every node.
We have create a Struct to hold the current diameter and current height of a Node.
Code is available here.
Time complexity is O(n), as we traverse through every node in the input Tree.
Space complexity is O(d), as we may hold length of the longest branch (d) in the input Tree in our call stack.