For example consider the below binary tree
The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7. In this example the longest path passes through the root node. Sometimes it may not pass through the root. Checkout the next example.
The longest path 27-28-24-36-42-59-55 does not include the root node.
Here is how we can find the longest path recursively. We know that the height of the binary tree is the longest path from the root node to any leaf node.(Read this post to know more). Diameter is the maximum of the following.
Height(left subtree) + Height(right subtree) + 1
Diameter(left subtree)
Diameter(right subtree)
Here is the C++ implementation of the above. This program calculates the number of nodes on the longest path. The time complexity for this solution is O(n2). For optimal implementation, you can checkout this post.
| #include <iostream> | |
| using namespace std; | |
| //Binary tree node type | |
| struct TreeNode | |
| { | |
| int val; | |
| TreeNode *left, *right; | |
| TreeNode(int v):val(v),left(NULL), right(NULL) | |
| { | |
| } | |
| }; | |
| //Binary search tree insert procedure for creating binary tree to test | |
| TreeNode* insert(TreeNode * root, int data) | |
| { | |
| if( root == NULL ) | |
| { | |
| root = new TreeNode(data); | |
| return root; | |
| } | |
| if( data < root->val ) | |
| root->left = insert( root->left, data ); | |
| else | |
| root->right = insert( root->right, data ); | |
| return root; | |
| } | |
| int height(TreeNode *root ) | |
| { | |
| if( root == NULL ) | |
| return 0; | |
| return max(height(root->left), height(root->right))+1; | |
| } | |
| int diameter(TreeNode *root ) | |
| { | |
| //Base cases | |
| if( root == NULL ) | |
| return 0; | |
| int lHeight = height(root->left); | |
| int rHeight = height(root->right); | |
| int lDiameter = diameter(root->left); | |
| int rDiameter = diameter(root->right); | |
| return max( lHeight+rHeight+1, max(lDiameter,rDiameter)); | |
| } | |
| void Test1() | |
| { | |
| TreeNode *root = NULL; | |
| root = insert(root, 2); | |
| root = insert(root, 1); | |
| root = insert(root, 3); | |
| cout << "Diameter: " << diameter(root) << endl; | |
| } | |
| void Test2() | |
| { | |
| TreeNode *root = NULL; | |
| root = insert(root, 1); | |
| root = insert(root, 2); | |
| root = insert(root, 3); | |
| cout << "Diameter: " << diameter(root) << endl; | |
| } | |
| int main() | |
| { | |
| Test1(); | |
| Test2(); | |
| return 0; | |
| } |
by