So this question asks us to find Number of Nodes on the Longest Path in Binary Tree so one thing is sure that this path comprises on two leaves with maximum distance in BT..isn't it
PS:Don't confused with finding the maximum distance between two nodes in Binary Tree(as it doesn't involves 2 leaves)
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with same 7 as a diameter but different orientation. (also note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
Diameter 7 in both cases
The diameter of a tree T is the largest of the following quantities:
Time Complexity O(n)
Space Complexity O(1)
PS:Don't confused with finding the maximum distance between two nodes in Binary Tree(as it doesn't involves 2 leaves)
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with same 7 as a diameter but different orientation. (also note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
Diameter 7 in both cases
The diameter of a tree T is the largest of the following quantities:
- the diameter of T’s left subtree
- the diameter of T’s right subtree
- the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
/* function to create a new node of tree and returns pointer */ Node newNode(int data); /* returns max of two integers */ int max(int a, int b); /* The function Compute the "height" of a tree. Height is the number f nodes along the longest path from the root node down to the farthest leaf node.*/ int height(Node node) { /* base case tree is empty */ if(node == NULL) return 0; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + max(height(node->left), height(node->right)); } /* Function to get diameter of a binary tree */ int diameter(Node tree) { /* base case where tree is empty */ if (tree == null) return 0; /* get the height of left and right sub-trees */ int lheight = height(tree->left); int rheight = height(tree->right); /* get the diameter of left and right sub-trees */ int ldiameter = diameter(tree->left); int rdiameter = diameter(tree->right); /* Return max of following three 1) Diameter of left subtree 2) Diameter of right subtree 3) Height of left subtree + height of right subtree + 1 */ return max(lheight + rheight + 1, max(ldiameter, rdiameter)); }
Time Complexity O(n)
Space Complexity O(1)
the complexity is O(n^2) . since each node is visit multiple times as the traversal is top bottom and not bottom up.
ReplyDelete